User theQman

4 votes

1 answer

186 views

Statement of the Goldwasser-Sipser Set Low Bound Protocol

asked Jan 5, 2021 at 18:10

1 vote

1 answer

65 views

Changing probabilities to 0/1 in definition of class IP

asked Mar 16, 2019 at 22:45

2 votes

0 answers

16 views

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

asked Mar 11, 2019 at 22:25

1 vote

1 answer

47 views

Alternative formulation of complexity class $BPP$

asked Nov 12, 2018 at 18:03

0 votes

0 answers

30 views

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

asked Nov 9, 2018 at 15:29

3 votes

1 answer

667 views

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

asked Nov 3, 2018 at 13:27

0 votes

0 answers

185 views

Proof of the Cook-Levin Theorem - snapshot transitions

asked Sep 5, 2018 at 15:57

6 votes

1 answer

1k views

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

asked Sep 4, 2018 at 14:12

3 votes

1 answer

154 views

$TSAT$ is $NP$-complete

asked Aug 29, 2018 at 17:59

2 votes

1 answer

289 views

Time-constructible functions definition

asked Aug 29, 2018 at 0:50

6 votes

2 answers

283 views

Countably many oracle Turing machines?

asked Dec 20, 2016 at 13:55

6 votes

2 answers

1k views

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

asked Dec 19, 2016 at 2:35

3 votes

2 answers

3k views

Decision version of the traveling salesman problem and NP-hardness

asked Dec 12, 2016 at 20:20

2 votes

1 answer

37 views

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

asked Dec 12, 2016 at 18:11

0 votes

1 answer

106 views

Running time of naive primality tester

asked Nov 30, 2016 at 2:22

5 votes

1 answer

456 views

Why is the complement of SAT in IP?

asked Nov 3, 2016 at 16:21

1 vote

1 answer

83 views

Recognizing vs Deciding in defining class BPP

asked Nov 3, 2016 at 14:08

2 votes

1 answer

886 views

Understanding why ALL_nfa is in co-nspace

asked Nov 1, 2016 at 20:46

Stack Exchange Network

18 Questions

Statement of the Goldwasser-Sipser Set Low Bound Protocol

Changing probabilities to 0/1 in definition of class IP

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

Alternative formulation of complexity class $BPP$

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

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

Proof of the Cook-Levin Theorem - snapshot transitions

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

$TSAT$ is $NP$-complete

Time-constructible functions definition

Countably many oracle Turing machines?

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

Decision version of the traveling salesman problem and NP-hardness

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

Running time of naive primality tester

Why is the complement of SAT in IP?

Recognizing vs Deciding in defining class BPP

Understanding why ALL_nfa is in co-nspace