期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
