On the Query Complexity of Clique Size and Maximum Satisfiability

• Author: R. Chang.
• Cite as: Journal of Computer and System Sciences, 53(2):298-313, October 1996.
• Other incarnations:
  • In Proceedings of the 9th Structure in Complexity Theory Conference, 31-42, June 1994.
  • Technical Report TR-CS-95-01, Department of Computer Science, University of Maryland Baltimore County, April 1995.
• Most readable version: journal version (there are small bugs in the TR version).
• Status: complete.
• Online:
  • Article on Elsevier's Science Direct: DOI 10.1006/jcss.1996.0070.
  • Final journal submission availabe as a PDF file (with embedded Type 1 fonts): approx2.pdf.

Abstract:

This paper explores the bounded query complexity of approximating the size of the maximum clique in a graph (Clique Size) and the number of simultaneously satisfiable clauses in a 3CNF formula (MaxSat). The results in the paper show that for certain approximation factors, approximating Clique Size and MaxSat are complete for corresponding bounded query classes under metric reductions. The completeness result is important because it shows that queries and approximation are interchangeable: NP queries can be used to solve NP-approximation problems and solutions to NP-approximation problems answer queries to NP oracles. Completeness also shows the existence of approximation preserving reductions from many NP-approximation problems to approximating Clique Size and MaxSat (e.g., from approximating Chromatic Number to approximating Clique Size). Since query complexity is a quantitative complexity measure, these results also provide a framework for comparing the complexities of approximating Clique Size and approximating MaxSat. In addition, this paper examines the query complexity of the minimization version of the satisfiability problem, MinUnsat, and shows that the complexity of approximating MinUnsat is very similar to the complexity of approximating Clique Size. Since MaxSat and MinUnsat share the same solution space, the "approximability" of MaxSat is not due to the intrinsic complexity of satisfiability, but is an artifact of viewing the approximation version of satisfiability as a maximization problem.