Working in an extremely flexible framework, this paper investigates the notion of nonuniform computation. Given a function f : N → N, a set B ⊆ { ⟨ O n , u ⟩ | length ( u ) = f ( n ) } is called an f-set. The triplet ( I , B , f ), with B an f-set, is a nonuniform proof system (PS) for a language A if, for all b, a string u exists with length( u ) = f ( n ) and ⟨ O n , u ⟩ ∈ B, and for all natural numbers n, for all strings u with ( u ) = f ( n ), ⟨ O n , u ⟩ ∈ B implies A ≤ n = { x | ⟨ x , u ⟩ ∈ I }. The three components of a nonuniform proof system are called, respectively, the interpretation set, the proof set, and the length function. The paper limits itself to length functions growing polynomially.
For two language classes C1 and C2, C1-C2-PSL (proof system language) denotes the class of all sets A for which a proof system with an interpretation set from C1 and a proof set from C2 exists. For example, P/Poly=P-P&Sgr;-PSL, where P&Sgr; denotes the class of all languages over a given alphabet &Sgr;. The author proves a general lowness result, from which most of the known lowness results can be derived: ( ( Co-NP ) -&Sgr; kp - PSL ) ∩ NP ⊆ L kp. (The notation is standard; see Schöning [1].)
Two particular types of nonuniform PSs are investigated: the secure PS, which allows only one-sided error when advice strings not belonging to the proof set are considered, and the dense PS, whose proof set contains the majority of all advice strings of appropriate length. Secure PSs are used for the study of classes such as APT and the P-selective sets, while dense PSs are used to describe probabilistic complexity classes.
Although the proof techniques used are not new, the proposed framework leads to some interesting new results.
