The complexity of optimization problems

Summary

The central result is that any FPSAT function decomposes into an OptP function followed by polynomial-time computation, and it quantifies "how much" NP-completeness is in a problem, i.e., the number of NP queries it takes to compute the function.

Keywords

Citation, Computer science, Library science, World Wide Web, Operations research

References

The Design and Analysis of Computer AlgorithmsAlfred V. Aho, John E. Hopcroft — 1974
The complexity of facets (and some facets of complexity)Christos H. Papadimitriou, Mihalis Yannakakis — 1982
Relativizations of the P =? NP QuestionT. P. Baker, John Gill, Robert M Solovay — 1975
The Complexity of Computing the PermanentLeslie G. Valiant — 1979
Computers and Intractability: A Guide to the Theory of NP-CompletenessM. R. Garey, David S. Johnson — 1979
On isomorphisms and density of NP and other complete setsJuris Hartmanis, L. Berman — 1976
NP is as easy as detecting unique solutionsLeslie G. Valiant, Vijay V. Vazirani — 1985
The Complexity of Near-Optimal Graph ColoringM. R. Garey, David S. Johnson — 1976
Some Simplified NP-Complete Graph ProblemsM. R. Garey, David S. Johnson, Larry Stockmeyer — 1976
The complexity of theorem-proving proceduresStephen Cook — 1971
The Polynomial-Time HierarchyLarry J. Stockmeyer — 1976
On the complexity of unique solutionsPAPADIMITRIOU, CH — 1982
An efficient approximation scheme for the one-dimensional bin-packing problemNarendra Karmarkar, Richard M. Karp — 1982
The NP-Completeness Column: An Ongoing GuideDavid S. Johnson — 1982
The NP-completeness column: An ongoing guideDavid S. Johnson — 1984
On the complexity of unique solutionsChristos H. Papadimitriou — 1982
Reducibility Among Combinatorial ProblemsR. Karp — 1972

Cited by

Structure in Approximation Classes (Extended Abstract)Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri — 1995
Compiling Control Knowledge into Preconditions for Planning in the Situation CalculusAlfredo Gabaldon — 2003
On Approximation Preserving Reductions: Complete Problems and Robust Measures (Revised Version)Pekka Orponen, Heikki Mannila — 1987
Semantical and Computational Aspects of Horn ApproximationsMarco Cadoli, Francesco Scarcello — 1993
Query Order and Self-Specifying MachinesLane A. Hemaspaandra, Harald Hempel⋆, Gerd Wechsung — 1995
Design and implementation of exact max-sat solversJordi Planes — 2007
The Complexity of Optimal Planning and a More Efficient Method for Finding SolutionsKatrina J. Ray, Matthew L. Ginsberg — 2008
Economics and Computation: Ad Auctions and Other StoriesChristopher A. Wilkens — 2013
Unambiguous logarithmic space bounded computationsVinodchandran N. Variyam, Raghunath Tewari — 2011
Model-based Revision Operators for Terminologies in Description LogicsGuilin Qi, Jianfeng Du — 2009
On the Structure of NP Computations under Boolean OperatorsRichard Chang — 1991
The Complexity of Belief UpdatePaolo Liberatore — 1997
Solving Weighted Max-SAT Problems in a Reduced Search Space: A Performance AnalysisKnot Pipatsrisawat, Akop Palyan, Mark Chavira — 2008
Query-limited reducibilitiesRichard Beigel — 1988
The Complexity of Temporal Logic Model CheckingPhilippe Schnoebelen — 2002
A Note on the Karp-Lipton Collapse for the Exponential HierarchyChris Bourke — 2007
Logspace Optimisation Problems and their Approximation PropertiesTill Tantau — 2003
Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization ProblemsTomoyuki Yamakami — 2013
A Machine Model for NP-Approximation Problems and the Revenge of the Boolean HierarchyRichard Chang — 1994
Reductions between disjoint NP-pairsChristian Glaßer, Alan L. Selman, Samik Sengupta — 2004

Related papers

ИСПОЛЬЗОВAНИЕ ПОТЕНЦИAЛA СОЦИAЛЬНЫХ ПAРТНЕРОВ В ПОДГОТОВКЕ БУДУЩИХ ПЕДAГОГОВБ.Б. Атaбекова — 2024
DETERMINING QUALITY REQUIREMENTS AT THE UNIVERSITIES TO IMPROVE THE QUALITY OF EDUCATIONNor Hanim Mustafa, Dinmukhamed Kelesbayev, Zh.D. Alibekova — 2018
Using DataGrid Control to Realize DataBase of Querying in VB6.0Shu Hu — 2000
ESKVS: efficient and secure approach for keyframes-based video summarization frameworkParul Saini, Krishan Berwal — 2024
Study and Two Types of Typical Usage of DataGrid Web Server ControlLuo Hai-tao — 2005
STKVS: secure technique for keyframes-based video summarization modelParul Saini, Krishan Berwal, Shamal Kashid — 2024
PACWON: A parallelizing compiler for workstations on a networkDibyendu Das, Partha Pratim Das — 1998
SLA Aware Optimized Task Scheduling Model for Faster Execution of Workloads Among Federated CloudsDivya Kshatriya, Vijayalakshmi A. Lepakshi — 2024