##
**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.

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

### MSC:

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 |