Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NP-APPROXIMATION PROBLEMS:
Reports tagged with NP-approximation Problems:
TR97-035 | 31st July 1997
Richard Chang

Bounded Queries, Approximations and the Boolean Hierarchy

Revisions: 1

This paper introduces a new model of computation for describing the
complexity of NP-approximation problems. The results show that the
complexity of NP-approximation problems can be characterized by classes of
multi-valued functions computed by nondeterministic polynomial time Turing
machines with a bounded number of oracle queries to an NP-complete
language. ... more >>>




ISSN 1433-8092 | Imprint