Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly

Webpage for a paper by Oded Goldreich and Or Meir


Abstract

An input-oblivious proof system is a proof system in which the proof does not depend on the claim being proved. Input-oblivious versions of NP and MA were introduced in passing by Fortnow, Santhanam, and Williams (CCC 2009), who also showed that those classes are related to questions on circuit complexity.

In this note we wish to highlight the notion of input-oblivious proof systems, and initiate a more systematic study of them. We begin by describing in detail the results of Fortnow et al., and discussing their connection to circuit complexity. We then extend the study to input-oblivious versions of IP, PCP, and ZK, and present few preliminary results regarding those versions.

Abstract (v.o.)

We initiate a study of input-oblivious proof systems, and present a few preliminary results regarding such systems. Our results offer a perspective on the intersection of the non-uniform complexity class $\Ppoly$ with uniform complexity classes such as $\NP$ and $\IP$. In particular, we provide a uniform complexity formulation of the conjecture $\NP\not\subset\Ppoly$ and a uniform complexity characterization of the class $\IP\cap\Ppoly$. These (and similar) results offer a perspective on the attempt to prove circuit lower bounds for complexity classes such as $\NP$, $\PSPACE$, $\EXP$, and $\NEXP$.

Comment: Andy Drucker has just brought to our attention that the classes ONP and OMA were defined and studied in the prior work of Lance Fortnow, Rahul Santhanam, and Ryan Williams "Fixed-Polynomial Size Circuit Bounds" (IEEE Conference on Computational Complexity, pages 19-26, 2009). Their paper contains many of our observations, most importantly the main part of our Thm 1.1 appears in Sec II.B.

Material available on-line


Back to either Oded Goldreich's homepage or general list of papers.