Title :
On the query complexity of clique size and maximum satisfiability
Author_Institution :
Dept. of Comput. Sci., Maryland Univ., Baltimore, MD, USA
fDate :
28 Jun- 1 Jul 1994
Abstract :
The 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 (MAX3SAT). The results show that for certain approximation factors, approximating clique size and MAX3SAT 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 MAX3SAT (e.g., from approximating chromatic number to approximating clique size). Finally, since query complexity is a quantitative complexity measure, these results also provide a framework for comparing the complexities of approximating clique size and approximating MAX3SAT
Keywords :
approximation theory; computational complexity; graph theory; optimisation; 3CNF formula; MAX3SAT; NP oracles; NP queries; NP-approximation problems; approximation factors; approximation preserving reductions; bounded query classes; bounded query complexity; chromatic number; clique size; completeness result; maximum clique; maximum satisfiability; metric reductions; quantitative complexity measure; simultaneously satisfiable clauses; Computer science; Polynomials; Size measurement; Turing machines;
Conference_Titel :
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location :
Amsterdam
Print_ISBN :
0-8186-5670-0
DOI :
10.1109/SCT.1994.315820
