Title :
On ultrafilters and NP
Author :
Ben-David, S. ; Karchmer, M. ; Kushilevitz, E.
Author_Institution :
Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel
fDate :
28 Jun- 1 Jul 1994
Abstract :
The fusion method (A. Wigderson, 1993) is developed by exploring its similarities with the ultraproduct construction in model theory. We use this analogy to re-prove a result of M. Sipser (1984) regarding countable circuits, in a simpler way. In the finite case this analogy allows us to give a new characterization of co-NP in terms of the CLIQUE function. This gives a natural interpretation to the NP-completeness of the CLIQUE function
Keywords :
computational complexity; filtering and prediction theory; modelling; networks (circuits); switching functions; CLIQUE function; NP-completeness; co-NP; countable circuits; fusion method; model theory; ultrafilters; ultraproduct construction; Approximation methods; Boolean functions; Circuits; Computer science; Contracts; Mathematics;
Conference_Titel :
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location :
Amsterdam
Print_ISBN :
0-8186-5670-0
DOI :
10.1109/SCT.1994.315813
