Class Description

PFCHK(t(n)): Proof-Checker

The class of decision problems solvable in time O(t(n)) by a nondeterministic Turing machine, as follows. The machine is given oracle access to a proof string of unbounded length.

Credited in [For94] to S. Arora, R. Impagliazzo, and U. Vazirani.

An interesting question is whether NP = PFCHK(log n) relative to all possible oracles. Fortnow [For94] observes that the answer depends on what oracle access mechanism is used.

Linked From

No class.