Skip to main content
Share Your Experience: Take the 2024 Developer Survey
theQman's user avatar
theQman's user avatar
theQman's user avatar
theQman
  • Member for 7 years, 7 months
  • Last seen more than 3 years ago
4 votes
1 answer
181 views

Statement of the Goldwasser-Sipser Set Low Bound Protocol

1 vote
1 answer
62 views

Changing probabilities to 0/1 in definition of class IP

2 votes
0 answers
15 views

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

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

3 votes
1 answer
642 views

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

0 votes
0 answers
184 views

Proof of the Cook-Levin Theorem - snapshot transitions

6 votes
1 answer
1k views

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

3 votes
1 answer
151 views

$TSAT$ is $NP$-complete

2 votes
1 answer
276 views

Time-constructible functions definition

6 votes
2 answers
269 views

Countably many oracle Turing machines?

6 votes
2 answers
1k views

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

3 votes
2 answers
3k views

Decision version of the traveling salesman problem and NP-hardness

2 votes
1 answer
37 views

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

0 votes
1 answer
103 views

Running time of naive primality tester

5 votes
1 answer
448 views

Why is the complement of SAT in IP?

1 vote
1 answer
79 views

Recognizing vs Deciding in defining class BPP

2 votes
1 answer
840 views

Understanding why ALL_nfa is in co-nspace