A Machine Model for the Complexity of NP-approximation Problems


This paper investigates a machine-based model for the complexity of approximating the CLIQUE problem. The model consists of nondeterministic polynomial time Turing machines with limited access to an NP-complete oracle. Approximating the CLIQUE problem is complete for classes of functions computed by such machines.

Last Modified: 29 Oct 2007 21:14:17 EDT by Richard Chang