Non-uniform proof-systems: A new framework to describe non-uniform and probabilistic complexity classes.

*(English)*Zbl 0666.68047
Foundations of software technology and theoretical computer science, Proc. 8th Conf., Pune/India 1988, Lect. Notes Comput. Sci. 338, 193-210 (1988).

[For the entire collection see Zbl 0656.00031.]

The concept of non-uniform proof systems is introduced. This notion allows a uniform description of non-uniform complexity classes, probabilistic classes (e.g. BPP) and language classes defined by simultaneous non-uniform and nondeterministic time bounds. Non-uniform proof systems provide a better understanding of many results concerning these classes, particularly their connections to uniform complexity measures.

We give an uniform approach to lowness results for various complexity classes. For instance, we show that co-NP/Poly\(\cap NP\) is contained in the third level of the low hierarchy and that, NP\(\subseteq (NP\cap co\)- NP)/Poly implies that the polynomial time hierarchy collapses to its second level. Finally, some evidence is given that the low hierarchy cannot be extended beyond its third level by the current techniques.

The concept of non-uniform proof systems is introduced. This notion allows a uniform description of non-uniform complexity classes, probabilistic classes (e.g. BPP) and language classes defined by simultaneous non-uniform and nondeterministic time bounds. Non-uniform proof systems provide a better understanding of many results concerning these classes, particularly their connections to uniform complexity measures.

We give an uniform approach to lowness results for various complexity classes. For instance, we show that co-NP/Poly\(\cap NP\) is contained in the third level of the low hierarchy and that, NP\(\subseteq (NP\cap co\)- NP)/Poly implies that the polynomial time hierarchy collapses to its second level. Finally, some evidence is given that the low hierarchy cannot be extended beyond its third level by the current techniques.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

03D15 | Complexity of computation (including implicit computational complexity) |