28
$\begingroup$

In a lot of domains, there are canonical techniques which everybody working in the field should master. For example, for logspace reductions, the "bit trick" for composition consisting of not constructing the full output of the composed function, but always asking to recompute the result for every bit of output, permitting to keep logspace constraints.

My question is about non-relativizing techniques. Do theoricians have outlined some fundamental non-relativizing operations, or is there a different trick for each known non-relativizing proof ?

$\endgroup$
  • $\begingroup$ maybe one concept central to (non-)relativization is "compression algorithms" $\endgroup$ – vzn Sep 19 '12 at 3:49
  • $\begingroup$ what is abstract device according to Automata $\endgroup$ – user32428 Mar 16 '15 at 2:57
40
$\begingroup$

There's really only one "flagship" non-relativizing technique: namely, arithmetization (the technique used in the proofs of IP=PSPACE, MIP=NEXP, PP⊄SIZE(nk), MAEXP⊄P/poly, and several other results).

However, the proof that all NP languages have computational zero-knowledge proofs (assuming one-way functions exist), due to Goldreich, Micali, and Wigderson, used a different non-relativizing technique (namely, the symmetries of the 3-COLORING problem).

Arora, Impagliazzo, and Vazirani argued that even "local checkability," the property of NP-complete problems used in the proof of the original Cook-Levin Theorem (as well as the PCP Theorem), should count as a non-relativizing technique (though Lance Fortnow wrote a paper arguing the opposite). The sticking point is whether it makes sense to relativize the complexity class of "locally checkable problems."

The pebbling arguments used in results from the 1970s such as TIME(n)≠NTIME(n) have been put forward as another example of a non-relativizing technique.

For more, you might want to check out my algebrization paper with Wigderson, and especially the references therein. We had to pretty much catalogue the existing non-relativizing techniques in order to figure out which ones were and weren't encompassed by the algebrization barrier.

Addendum: I just realized that I forgot to mention measurement-based quantum computing (MBQC), which was recently used to great effect by Broadbent, Fitzsimons, and Kashefi to obtain quantum complexity theorems (such as QMIP = MIP*, and BQP = MIP with entangled BQP provers and BPP verifier) that most likely fail to relativize.

$\endgroup$

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.