Are there interactive protocols for co-NP languages? (Q1118406): Difference between revisions

An interactive protocol is a game (dialogue) between an infinitely powerful prover and a probabilistic polynomial time verifier. A language L has an interactive protocol when the proper can convince the verifier to accept a strong x if and only if x belongs to the language L. The authors conjecture that co-NP problems do not have interactive protocols. This problem is open and as hard as \({\mathcal P}\neq {\mathcal N}{\mathcal P}\). It is shown in this paper that there exist an oracle and a language in co-NP that does not have an interactive protocol relative to this oracle. It implies that techniques that relativize will not settle the mentioned above conjecture.