The tag has no wiki summary.

learn more… | top users | synonyms

-1
votes
1answer
184 views

equivalent way(s) of expressing P=?NP problem in linear programming?

the paper "In defense of the Simplex Algorithm's worst-case behavior" Disser/Skutella [1] was recently cited on this tcs.se site by saeed on another interesting question. the paper introduces the idea ...
9
votes
2answers
302 views

Barriers to separating other complexity classes

Do Natural Proofs, Relativization and Algebrization also affect separation of other complexity classes like $L\neq NL\neq NP\neq coNP \neq PH\neq PSPACE$ etc? For instance natural proofs barrier ...
9
votes
0answers
415 views

Has there been any result which does not have any Natural Proofs?

Alexander Razborov and Steven Rudich's Natural Proofs result is one of the major barriers against proving circuit lower bounds. The paper is almost 20 years old (it was published in 1994). Has there ...
10
votes
2answers
234 views

Is there an explanation for the difficulty of proving quadratic lower bounds for interesting NP problems?

This is a follow up to my previous question: Best known deterministic time complexity lower bound for a natural problem in NP I find it bewildering that we haven't been able to prove any quadratic ...
26
votes
1answer
625 views

Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

Many believe that $\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$. However we only know that $\mathsf{BPP}$ is in the second level of polynomial hierarchy, i.e. $\mathsf{BPP}\subseteq \Sigma^ ...
24
votes
3answers
636 views

Constructivity in Natural Proof and Geometric Complexity

Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$. Constructivity in Natural ...
26
votes
1answer
842 views

Toy examples for barriers to $P \ne NP$

Are there any toy examples that provide 'essential' insights into understanding the three known barriers to $P = NP$ problem - relativization, natural proofs and algebrization?
8
votes
4answers
529 views

Does diagonalization captures the essence of class separation ?

I don't remember having seen a class separation not based on diagonalization and relativization results. Diagonalization could still be used to separate remaining known classes, because ...
14
votes
2answers
766 views

Barriers and Monotone Circuit Complexity

Natural proofs is a barrier towards proving lower bounds on the circuit complexity of boolean functions. They do not directly imply any such barrier in proving lower bounds on the $monotone$ circuit ...
19
votes
3answers
853 views

Proofs, Barriers and P vs NP

It is well known that any proof resolving the P vs NP question must overcome relativization, natural proofs and algebrization barriers. The following diagram partitions the "proof space" into ...
20
votes
2answers
995 views

How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about ...