Math 2.0

Computer science Computational complexity: resources and classes Theorem

Natural proofs barrier

Builds on P/polyCircuit complexityBoolean function

Statement

For n≥1n \ge 1 let FnF_n be the set of Boolean functions f ⁣:{0,1}n→{0,1}f \colon \set{0,1}^n \to \set{0,1}, and write N=2nN = 2^n. A combinatorial property is a sequence 𝒞=(Cn)\mathcal{C} = (C_n) with Cn⊆FnC_n \subseteq F_n. It is P/poly-natural if some Cn∗⊆CnC_n^* \subseteq C_n satisfies:

  1. (constructivity) membership f∈Cn∗f \in C_n^* is decided by Boolean circuits of size polynomial in NN that read the truth table of ff;
  2. (largeness) ∣Cn∗∣≥2−O(n)∣Fn∣\abs{C_n^*} \ge 2^{-O(n)} \abs{F_n}.

It is useful against P/poly if every sequence fn∈Fnf_n \in F_n with fn∈Cnf_n \in C_n for infinitely many nn has circuit size not bounded by any polynomial in nn.

Assume that, for some ε>0\varepsilon > 0, there is a family of pseudorandom functions computed by polynomial-size circuits with the following hardness. No circuit of size 2nε2^{n^\varepsilon} distinguishes them from a uniformly random function with advantage at least 2−nε2^{-n^\varepsilon}. Then no P/poly-natural property is useful against P/poly.

Remarks

The idea of the proof is that a natural property useful against P/poly would itself be a distinguisher. Pseudorandom functions have small circuits, so they lie outside Cn∗C_n^*, while a random function lies in Cn∗C_n^* with probability at least 2−O(n)2^{-O(n)}. The constructive test for Cn∗C_n^* then tells the two apart, in time polynomial in N=2nN = 2^n, which contradicts the hardness assumption. The hypothesis is believed true; it follows from strong enough versions of standard cryptographic assumptions, such as the hardness of factoring.

Most known circuit lower bounds, such as parity not in AC0, are proved through properties that are natural in this sense, against weaker circuit classes. So the theorem says that proving NP⊈P/poly\mathrm{NP} \not\subseteq \mathrm{P/poly} needs an argument of a different kind.

Going deeper

For a student

The barrier appeared in 1994 in a paper of Alexander Razborov and Steven Rudich. It explains why the progress on lower bounds for restricted classes, such as AC0 and monotone circuits, did not extend to general circuits. Together with relativization and algebrization, it is one of the main known obstacles to proving P≠NP\mathrm{P} \ne \mathrm{NP}. Some lower bounds avoid it, for example those proved by diagonalisation, which use no large property.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Boolean function, concept, no evidence levelBoolean functionconceptCircuit complexity, concept, no evidence levelCircuit complexityconceptP/poly, concept, no evidence levelP/polyconceptNatural proofs barrier, statement, no evidence levelNatural proofs barrierstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Boolean function concept
  2. Circuit complexity concept
  3. P/poly concept
  4. Natural proofs barrier statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Natural_proof
About this page
TagTHPBBYSDP1
URIm2://THPBBYSDP1
Kindstatement, theorem
WritingW0 stub
MSC68Q17, 68Q06, 94A60
StatusThis copy of the site has no build data. Run m2 status THPBBYSDP1.
AboutCircuit complexity
UsesP/poly, Circuit complexity, Boolean function
Same as
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.