The barriers tag has no wiki summary.
8
votes
0answers
322 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 ...
7
votes
2answers
173 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 ...
23
votes
1answer
425 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^ ...
23
votes
3answers
548 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 ...
25
votes
1answer
753 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?
7
votes
4answers
464 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
697 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 ...
18
votes
3answers
755 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
821 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 ...
