On the Boolean closure of NP. (English) Zbl 0581.68043

Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 485-493 (1985).
[For the entire collection see Zbl 0568.00020.]
The paper presents several characterizations of the Boolean closure of NP, which is denoted by BC(NP), and consists of all the sets that can be obtained from sets from NP by taking complement, union and intersection. The closure of NP w.r.t. bounded truth table reducibility is exactly BC(NP) which is also contained in \(\Delta^ P_ 2\). The main purpose of the paper is to describe BC(NP) by some modification of alternating Tuing machines. The polynomial time classes of these machines are exactly the levels of BC(NP) which can be defined in some natural way.
Reviewer: A.Slisenko


68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
03D10 Turing machines and related notions
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D20 Recursive functions and relations, subrecursive hierarchies


Zbl 0568.00020