advocateofnone's user avatar
advocateofnone's user avatar
advocateofnone's user avatar
advocateofnone
  • Member for 9 years, 2 months
  • Last seen more than a week ago
27 votes
6 answers
8k views

Can input to a Turing machine be of infinite length?

20 votes
2 answers
4k views

How to find the element of the Digit Sum sequence efficiently?

11 votes
1 answer
3k views

How can I show that the Cook-Levin theorem does not relativize?

11 votes
3 answers
9k views

Can a regular expression be infinite?

9 votes
1 answer
3k views

Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

8 votes
2 answers
2k views

How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly} $ then $\textsf{EXP} = \Sigma^p_2$

6 votes
1 answer
7k views

Why is ZPP = RP ∩ co-RP?

6 votes
1 answer
607 views

How do incompressible strings and random strings share the same properties?

5 votes
1 answer
553 views

What is the complexity of finding a regular expression equivalent to a given DFA?

5 votes
1 answer
1k views

How to show ExactOneSAT is NP-Complete?

5 votes
2 answers
6k views

Why won't a Turing machine halt?

5 votes
1 answer
7k views

Can a Turing machine have infinite states?

5 votes
1 answer
217 views

Is there a decidable problem which has a proof that it cannot be proved to have a particular deciding Turing machine?

5 votes
1 answer
3k views

Why is simulation by non deterministic Turing machine faster than a deterministic one?

5 votes
1 answer
157 views

Implication of Berman and Hartmanis conjecture

4 votes
1 answer
686 views

Finding a kernel for d-Bounded degree deletion

4 votes
1 answer
125 views

Why is my trivial reasoning for $PSPACE = PH$ wrong?

4 votes
1 answer
87 views

Why there is no constraint on "Prover" in definition of $IP$?

4 votes
1 answer
272 views

How to compute the sum of this series involving golden ratio, efficiently?

4 votes
1 answer
2k views

Mapping reducibility vs. Turing reducibility

4 votes
1 answer
471 views

What does Godels Incompleteness theorem "true but unprovable" mean?

3 votes
1 answer
241 views

When does a PDA split?

3 votes
1 answer
389 views

How is the space hierarchy theorem different for non space constructible functions?

3 votes
2 answers
859 views

Is the language of TMs that decide some language Turing-recognizable?

3 votes
2 answers
2k views

set with maximum sum consisting of mutually co-prime numbers

3 votes
1 answer
1k views

How do I prove Berman's theorem?

3 votes
1 answer
56 views

Comparing different versions of Steiner Connected Component Subgraph problem

2 votes
1 answer
242 views

2-Approximation algorithm for for messages across a cyclic network

2 votes
2 answers
359 views

Maximum weight perfect matching in general graphs

2 votes
1 answer
392 views

Why is universal turing machine considered with only one head?