TransWikia.com
  1. All Categories
  2. Theoretical Computer Science

Theoretical Computer Science : Recent Questions and Answers (Page 5)

Find answers to your questions about Theoretical Computer Science or help others by answering their Theoretical Computer Science questions.

What does it mean by the statement: "a problem is hard to approximate "?

In most of the research papers that I have read so far, I often come across the statement of the following form: "the problem is hard to approximate within any...

Asked on 02/11/2021 by Inuyasha Yagami

0 answer

Reference request: DFA linear-time minimization

What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time? Here’s what I’ve been able to find so far:The acyclic case has...

Asked on 01/23/2021 by ShyPerson

0 answer

Proof of $LP$ is in $coNP$ without showing it is in $P$?

Is there a proof that linear programming is in $coNP$ without showing it is in $P$? If so what is the strategy?...

Asked on 01/19/2021

1 answer

Computing chromatic number of subcubic graphs

According to graphclasses.org, the chromatic number of a subcubic graph can be computed in linear time (because the decision problem COLORABILITY can be solved in linear time)....

Asked on 01/13/2021 by Cyriac Antony

0 answer

What math courses should I revisit to prepare for a CS Ph.D. (Reinforcement learning and Game Theory)?

I am planning to join a CS Ph.D. program in 6 months. My topics of research will be in the area of Reinforcement Learning and Game Theory. Even though I...

Asked on 01/07/2021

1 answer

A clear and rigorous explanation of critical pairs and the Knuth-Bendix completion algorithm?

I'm looking for an explanation of critical pairs and the Knuth-Bendix completion algorithm that is at once rigorous and of high pedagogical value, i.e. clear, detailed, containing illustrative examples preferably...

Asked on 12/11/2020 by Evan Aad

2 answer

Büchi automata with acceptance strategy

The problemLet $A=langle Sigma, Q, q_0,F,Deltarangle$ be a Büchi automaton, recognizing a language $LsubseteqSigma^omega$.We assume that $A$ has an acceptance strategy in the following sense :...

Asked on 11/26/2020

2 answer

Reference request: Depth- (or Breadth-) first search with hints?

Consider the standard s-t reachability problem of finding a path between nodes $s$ and $t$ in a directed graph $G$. A DFS or BFS could solve it....

Asked on 11/16/2020 by wei wang

1 answer

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP