theQman's user avatar
theQman's user avatar
theQman's user avatar
theQman
  • Member for 7 years, 5 months
  • Last seen more than 3 years ago
6 votes
2 answers
1k views

Why is the language of TMs that have some quadratic time bound undecidable?

6 votes
2 answers
267 views

Countably many oracle Turing machines?

6 votes
1 answer
1k views

Why not polynomial-space reductions for $PSPACE$-hardness?

5 votes
1 answer
447 views

Why is the complement of SAT in IP?

3 votes
2 answers
3k views

Decision version of the traveling salesman problem and NP-hardness

3 votes
1 answer
151 views

$TSAT$ is $NP$-complete

3 votes
1 answer
168 views

Statement of the Goldwasser-Sipser Set Low Bound Protocol

2 votes
0 answers
15 views

Motivation behind the definition of order-$k$ (edge) expansion?

2 votes
1 answer
631 views

Circuits vs Turing Machines in the "nonuniform model of computation"

2 votes
1 answer
37 views

Providing $1^n$ as input to protect against degenerate cases

2 votes
1 answer
266 views

Time-constructible functions definition

2 votes
1 answer
823 views

Understanding why ALL_nfa is in co-nspace

1 vote
1 answer
78 views

Recognizing vs Deciding in defining class BPP

1 vote
1 answer
60 views

Changing probabilities to 0/1 in definition of class IP

1 vote
1 answer
44 views

Alternative formulation of complexity class $BPP$

0 votes
0 answers
29 views

Every circuit of size at most $S$ can be representd as a string of $9S \log S$ bits

0 votes
0 answers
184 views

Proof of the Cook-Levin Theorem - snapshot transitions

0 votes
1 answer
103 views

Running time of naive primality tester