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 P/poly with uniform complexity classes such as NP and IP.
In particular, we provide a uniform complexity formulation of the conjecture $NP\not\subset P/poly$ and a uniform complexity
characterization of the class $IP\cap P/poly$.
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.
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 paper 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 $\mathcal{IP}$, $\mathcal{PCP}$, and $\mathcal{ZK}$, and present few preliminary results regarding those versions.
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 P/poly with uniform complexity classes such as NP and IP.
In particular, we provide a uniform complexity formulation of the conjecture $NP\not\subset P/poly$ and a uniform complexity
characterization of the class $IP\cap P/poly$.
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.
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.
As pointed out by Thilo Mie, Definition 4.1 (OPCP) is correct so as
to explicitly upperbound the proof length (by a polynomial).
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.
Their definition followed a work of Chakaravarthy and Roy (STACS 2006),
who defined an input-oblivious version of ${\cal S}_2$.
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 \etal,
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.
The paper was revised in light of the comment posted on Feb 16.
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 P/poly with uniform complexity classes such as NP and IP.
In particular, we provide a uniform complexity formulation of the conjecture $NP\not\subset P/poly$ and a uniform complexity
characterization of the class $IP\cap P/poly$.
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.
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.
Our paper also defines input-oblivious versions (of IP, PCP and ZK) that were not considered in the prior work of Fortnow, Santhanam, and Williams, and contains several observations not made there.
Please ignore this revision (as well as the old abstract) for the time being. The correct revision will be posted shortly; it is a slight improvement over the 2nd revision.
