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, October 1994.
• 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.

Abstract:

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.