theQman's user avatar
theQman's user avatar
theQman's user avatar
theQman
  • Member for 7 years, 4 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
262 views

Countably many oracle Turing machines?

6 votes
1 answer
1k views

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

5 votes
1 answer
442 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
147 views

$TSAT$ is $NP$-complete

3 votes
1 answer
162 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
611 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
256 views

Time-constructible functions definition

2 votes
1 answer
801 views

Understanding why ALL_nfa is in co-nspace

1 vote
1 answer
74 views

Recognizing vs Deciding in defining class BPP

1 vote
1 answer
57 views

Changing probabilities to 0/1 in definition of class IP

1 vote
1 answer
43 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