13
$\begingroup$

As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles).

Virtually all proofs seem to be relativizable, though.

What are good examples of non relativizable proofs, of the sort that a P=NP/P≠NP proof would need to be, that are not trivial or contrived?

(I am not a recursion theorist, so please pardon the lack of citations.)

[EDIT: better mathoverflow post]

$\endgroup$
  • 6
    $\begingroup$ To copy over my suggestion from MO and get it out of the way: the canonical example I'm aware of is the proof of IP=PSPACE, where particularly the inclusion of PSPACE in IP is done by showing an interactive proof for a particular PSPACE-complete problem, a non-relativizable technique - particular problems don't relativize. $\endgroup$ – Steven Stadnicki Jan 9 '14 at 6:08
  • 5
    $\begingroup$ @AndrejBauer AFAIK, no, because there's no such thing as 'relativized TQBF' - in fact, there are oracles $A$ with $\mathrm{IP}^A\neq \mathrm{PSPACE}^A$, so the proof can't canonically relativize. $\endgroup$ – Steven Stadnicki Jan 9 '14 at 7:19
  • 4
    $\begingroup$ @Steven: Relativized TBQF can be formed by allowing oracle gates, rather than just (standard) logic gates. $\endgroup$ – user6973 Jan 9 '14 at 7:21
  • 3
    $\begingroup$ @RickyDemer Even still, the heart of the proof works by interpreting the formula as a low-degree polynomial, which doesn't carry through when you have (say) a uniformly random oracle gate. $\endgroup$ – Yonatan N Jan 9 '14 at 8:12
  • 1
    $\begingroup$ btw the P=?NP result on relativization is known as the Baker-Gill-Solovay 1975 theorem. the proof can also be found eg in Hopcroft/Ullman. @richerby/Sai there is no reason to migrate after both questions are already entered, its more for future reference. also note there seems to be no official stackexchange cross-site policy on crossposting (hence some confusion is understandable). $\endgroup$ – vzn Jan 10 '14 at 18:56
24
$\begingroup$

As Steven notes, the canonical example is $\mathsf{IP} = \mathsf{PSPACE}$. This collapse does not relativize, in the sense that there is an oracle $A$, subject to which $\mathsf{IP}^A \ne \mathsf{PSPACE}^A$. The intuition why the known proof of this result avoids the relativization barrier is that it uses arithmetization (Yonatan alluded to this in a comment): an interactive protocol for the $\mathsf{PSPACE}$-complete problem TQBF is given by considering an extension of a quantified boolean formula to a low-degree polynomial over a suitably large field. If we are given a relativized boolean formula (with oracle gates), such an extension does not exist.

There is a refinement of the relativization barrier -- algebrization -- due to Aaronson and Wigderson. Generically, the arithmetization technique is not enough to circumvent the algebrization barrier. A complexity class inclusion $\mathsf{C} \subseteq \mathsf{D}$ algebrizes if for any oracle $A$ and any extension $\tilde{A}$ of $A$ to low-degree polynomials over a finite field, $\mathsf{C}^A \subseteq \mathsf{D}^{\tilde{A}}$. A separation $\mathsf{C} \not \subset \mathsf{D}$ algebrizes if for all $A$, and all extensions $\tilde{A}$, $\mathsf{C}^{\tilde{A}} \not \subset \mathsf{D}^{A}$. Aaronson and Wigderson show that $\mathsf{IP} = \mathsf{PSPACE}$ algebrizes, but many other results, including $\mathsf{NP} \not \subset \mathsf{P}$, do not.

A recent example of a technique that does not algebrize or relativize is Ryan Williams' proof that $\mathsf{NEXP} \not \subset \mathsf{ACC}$. The separation does not algebrize: there is an oracle $A$ and a low-degree extension $\tilde{A}$ such that $\mathsf{NEXP}^{\tilde{A}} \subset \mathsf{ACC}^A$. Intuitively the reason why the proof avoids the barrier is that it relies on the existence of a faster-than-trivial satisfiability algorithm for $\mathsf{ACC}$ circuits, and the algorithm uses non-relativizing and non-algebrizing properties of such circuits. Ryan notes in the paper that all known faster-than-trivial satisfiability algorithms break down when oracles or algebraic extensions of oracles are added.

There is also an interesting approach to understanding relativization through logic. In an old manuscript, Arora, Impagliazzo, and Vazirani define a system of axioms such that the relativizing results are exactly those that follow from the axioms, while non-relativizing results are independent from the system. A paper by Impagliazzo, Kabanets, and Kolokolova does something similar for algebrization by introducing an additional axiom to the ones defined by Arora, Impagliazzo and Vazirani. They show that most known non-relativizing results follow from their axioms, while P vs NP, among others, is independent of them.

Apologies if I got something wrong, I am not quite an expert.

$\endgroup$
  • 7
    $\begingroup$ There are other examples on non-relativizing proofs in the Aaronson-Wigderson paper, such as $\textrm{NEXP} \subseteq \textrm{MIP}$, $\textrm{MA}_\textrm{EXP} \nsubseteq \textrm{P}/\textrm{poly}$, $\textrm{PromiseMA} \nsubseteq \textrm{SIZE}(n^k)$, etc. $\endgroup$ – Robin Kothari Jan 9 '14 at 16:14
10
$\begingroup$

Here is a list of non-relativizable proofs:

  1. The PCP Theorem

  2. Instance-dependent commitment implies zero-knowledge protocol:
    An Equivalence between Zero Knowledge and Commitments

  3. There is no efficient "virtual black box" circuit obfuscator for general circuits:
    An Equivalence between Zero Knowledge and Commitments

  4. PSPACE is reducible to evaluating a succinct product of $S_5$:
    PSPACe survives three-bit bottlenecks

  5. Against unentangled provers, NEXP has minimally-interactive 2-prover proof systems:
    Two-prover one-round proof systems: their power and their problems

  6. Against possibly-entangled provers, NEXP has more-interactive MIP protocols:
    A multi-prover interactive proof for NEXP sound against entangled provers

  7. NP has efficient-prover NISZK proofs-of-knowledge with perfect knowledge extraction in a "efficiently samplable non-standard distribution" hidden bits model, and efficient-prover NIPZK proofs-of-knowledge in the (real) hidden bits model. Furthermore, if the sampler is allowed to have a small probability of outputting $\perp$ (and soundness is only required to hold when the sampler doesn't output $\perp$), then "NISZK" from the previous sentence can be replaced with "NIPZK".
    Jonathan Katz, Advanced Topics in Cryptography, Lecture 13
    Note: Perfect knowledge-extraction follows by inspection of the soundness part on page 2. (Non-perfect) knowledge-extraction holds for the same reason as non-perfect soundness, as described at the top of page 5. Perfect zero-knowledge can be obtained by having the simulator use the Hamiltonian matrix $C_i$ as its permutation $\pi$, and some of the actual bit-strings corresponding to biased-bits with value 0 as themselves, just mostly in different locations. The "furthermore" sentence follows by having the sampler output $\perp$ if it was unable to choose an element from {0,1,2,3,...,n!-1} perfectly uniformly in a small enough amount of time, since such a choice would allow for the perfectly uniform generation of a directed cycle graph matrix or a permutation of the vertices.

$\endgroup$
7
$\begingroup$

this is a nice survey of the field by a leading expert that summarizes/details some of the points of the other answers so far & has additional examples.

[1] The Role of Relativization in Complexity Theory Fortnow

Several recent nonrelativizing results in the area of interactive proofs have caused many people to review the importance of relativization. In this paper we take a look at how complexity theorists use and misuse oracle results. We pay special attention to the new interactive proof systems and program checking results and try to understand why they do not relativize. We give some new results that may help us to understand these questions better.

$\endgroup$
  • 6
    $\begingroup$ +1 this is a nice survey, but it should be mentioned that it surveys the state of the world up to 1993 $\endgroup$ – Sasho Nikolov Jan 10 '14 at 17:05
  • $\begingroup$ true; it would be helpful if authors included dates in their papers more... a more recent survey would be helpful too, the topic seems rarely surveyed. this area does not seem to change so much & its not so clear how many new results have emerged since that date. $\endgroup$ – vzn Jan 10 '14 at 18:49
  • 3
    $\begingroup$ for new results: I think some new oracle results have appeared since that relate to quantum complexity classes. more importantly, there have been developments in terms of what oracle results mean: the algebrization barrier and Ryan's non-algebrizing proof from my answer, a related paper cs.sfu.ca/~kabanets/papers/act-full.pdf, and possibly Boaz Barak's work on non-black-box reductions in crypto. $\endgroup$ – Sasho Nikolov Jan 10 '14 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.