User argentpepper

49 votes

4 answers

2k views

What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

asked Nov 1, 2012 at 0:09

26 votes

1 answer

819 views

What is $\mathsf{NP}$ restricted to linear size witnesses?

asked May 9, 2012 at 17:55

20 votes

0 answers

489 views

Interesting PCP characterization of classes smaller than P?

asked Jul 18, 2012 at 18:54

12 votes

1 answer

187 views

What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$?

asked May 23, 2013 at 17:35

11 votes

1 answer

1k views

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

asked Mar 21, 2012 at 21:44

10 votes

1 answer

217 views

Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?

asked Jan 30, 2013 at 22:37

7 votes

0 answers

349 views

Does Dinur's proof of PCP Theorem imply a procedure for reconstructing a witness?

asked Apr 8, 2013 at 19:17

6 votes

1 answer

315 views

Approximation schemes for P-complete problems?

asked Jan 30, 2012 at 18:55

5 votes

0 answers

149 views

What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?

asked Jun 22, 2012 at 18:27

4 votes

0 answers

106 views

What is the query and randomness complexity for very efficient PCPs?

asked Feb 20, 2013 at 22:02

4 votes

0 answers

189 views

Complexity of computing logarithm of a prime power

asked Nov 7, 2012 at 5:45

4 votes

1 answer

192 views

What do you call the join of two optimization problems?

asked Jul 23, 2015 at 19:51

3 votes

0 answers

131 views

What is the problem of finding a largest subset of smallest Kolmogorov complexity?

asked Aug 7, 2015 at 18:02

3 votes

0 answers

144 views

Looking for an "additive" binary graph operation that preserves subgraphs of high degree

asked Jun 11, 2013 at 20:00

1 vote

0 answers

230 views

Is $\mathsf{NP}$ in $\mathsf{NNC}^1$?

asked Oct 30, 2015 at 20:47

Stack Exchange Network

15 Questions

What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

What is $\mathsf{NP}$ restricted to linear size witnesses?

Interesting PCP characterization of classes smaller than P?

What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$?

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?

Does Dinur's proof of PCP Theorem imply a procedure for reconstructing a witness?

Approximation schemes for P-complete problems?

What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?

What is the query and randomness complexity for very efficient PCPs?

Complexity of computing logarithm of a prime power

What do you call the join of two optimization problems?

What is the problem of finding a largest subset of smallest Kolmogorov complexity?

Looking for an "additive" binary graph operation that preserves subgraphs of high degree

Is $\mathsf{NP}$ in $\mathsf{NNC}^1$?