ON COMPUTING BOOLEAN CONNECTIVES OF CHARACTERISTIC FUNCTIONS

This paper is a study of the existence of polynomial time Boolean conn ective functions for languages. A language L has an AND function if th ere is a polynomial time f such that f(x,y) is an element of L double left right arrow x is an element of L and y is an element of L. L has an OR function if there is a polynomial time g such that g(x,y) is an element of L double left right arrow x is an element of L or y is an e lement of L. While all NP complete sets have these functions, Graph Is omorphism, which is probably not complete, is also shown to have both AND and OR functions. The results in this paper characterize the compl ete sets for the classes D-P and P-SAT[O(log n]) in terms of AND and O R, and relate these functions to the structure of the Boolean hierarch y and the query hierarchies. Also, this paper shows that the complete sets for the levels of the Boolean hierarchy above the second level ca nnot have AND or OR unless the polynomial hierarchy collapses. Finally , most of the structural properties of the Boolean hierarchy and query hierarchies are shown to depend only on the existence of AND and OR f unctions for the NP complete sets.