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.
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
29 Oct 2007 21:33:06 EDT