A Machine Model for the Complexity of NP-approximation Problems
- Author: R. Chang.
- Cite as:
In Current Trends in Theoretical Computer Science:
Entering the 21st Century,
G. Paun, G. Rozenberg and A. Salomaa, editors, pp. 4-24,
World Scientific, 2001.
- Previous incarnations:
"A Machine Model for NP-approximation Problems
and the Revenge of the Boolean Hierarchy,"
Bulletin of the European
Association of Theoretical Computer Science, 54:166-182,
- Most readable version: book version.
- Status: Book in print as of Feb 2001. Full proofs appear in
Bounded Queries, Approximations and
the Boolean Hierarchy.
- Online: book version available as a PDF file
(with embedded Type 1 fonts): revenge.pdf.
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.
29 Oct 2007 21:14:17 EDT