# The Complexity of Optimization Problems

@article{Krentel1988TheCO, title={The Complexity of Optimization Problems}, author={Mark W. Krentel}, journal={J. Comput. Syst. Sci.}, year={1988}, volume={36}, pages={490-509} }

Abstract We consider NP -complete optimization problems at the level of computing their optimal value, and define a class of functions called OptP to capture this level of structure. We show that TRAVELING SALESPERSON and KNAPSACK are complete for OptP , and that CLIQUE and COLORING are complete for a subclass of OptP . These results show a deeper level of structure in these problems than was previously known. We also show that OptP is closely related to FP SAT , the class of functions… Expand

#### Topics from this paper

#### 161 Citations

Quantifiers and Approximation

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1993

It is shown that many important optimization problems do not belong to MAX NP and that, in fact, there are problems in P which are not in MAX NP, and it is proved that several natural optimization problems are complete for MAX Π1 under approximation-preserving reductions. Expand

Quantifiers and approximation

- Mathematics, Computer Science
- STOC '90
- 1990

It is shown that many impor-taut optimization problems do not belong to MAX NP and that in fact there are problems in P which are not ill lk'IAX NP, and it is proved that several natural optimization problems are complete for MAX H1 under approxima. Expand

The Complexity of Selecting Maximal Solutions

- Computer Science, Mathematics
- Inf. Comput.
- 1995

This work studies maximality problems from the complexity point of view, and gives characterizations of coNP, DP, ?P2, FPNP||, FNP//OptP log n] and FP?P||2 in terms of subclasses of maximality Problems. Expand

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

- Computer Science, Mathematics
- Proceedings. 2004 International Conference on Information and Communication Technologies: From Theory to Applications, 2004.
- 2004

It is proved that the exact versions of the domatic number problem are complete for the levels of the Boolean hierarchy over NP, the 2kth level of the boolean hierarchy overNP. Expand

Structure in locally optimal solutions

- Mathematics, Computer Science
- 30th Annual Symposium on Foundations of Computer Science
- 1989

It is first shown that CNF (conjunctive normal form) satisfiability is PLS-complete, even with simultaneously bounded size clauses and bounded number of occurrences of variables, and this result is used to show that traveling salesman under the k-opt neighborhood is also P LS-complete. Expand

On the Complexity of Master Problems

- Computer Science
- MFCS
- 2015

It is shown that the master tour problem is \(\varDelta _2^p\)-complete in the scenario setting, that means, the subsets S are restricted to some given sets, and the master versions of Steiner tree and maximum weighted satisfiability are also \(\var delta _2 ^p\-complete, as is deciding whether the optimal solution for these problems is unique. Expand

On the query complexity of clique size and maximum satisfiability

- Mathematics, Computer Science
- Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory
- 1994

The results show that for certain approximation factors, approximating clique size and MAX3SAT are complete for corresponding bounded query classes under metric reductions, which shows that queries and approximation are interchangeable. Expand

On the Query Complexity of Clique Size and Maximum Satisfiability

- Mathematics, Computer Science
- J. Comput. Syst. Sci.
- 1996

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, showing that queries and approximation are interchangeable. Expand

Structural Complexity of Multiobjective NP Search Problems

- Computer Science
- LATIN
- 2012

Under the assumption that certain exponential time classes are different, it is shown that there are computational tasks of multiobjective problems (more precisely functions in NPMVg) that are Turing-inequivalent to any set. Expand

On bounded queries and approximation

- Mathematics, Computer Science
- Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science
- 1993

The results show a trade-off between the closeness of the approximation and the number of queries required, which holds when k(n) belongs to a class of functions which include any integer constant function, log n, log/sup a/ n and n/sup 1/a/. Expand

#### References

SHOWING 1-10 OF 14 REFERENCES

The complexity of optimization problems

- Mathematics, Computer Science
- STOC '86
- 1986

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. Expand

Some Simplified NP-Complete Graph Problems

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1976

This paper shows that a number of NP - complete problems remain NP -complete even when their domains are substantially restricted, and determines essentially the lowest possible upper bounds on node degree for which the problems remainNP -complete. Expand

An efficient approximation scheme for the one-dimensional bin-packing problem

- Mathematics, Computer Science
- 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)
- 1982

It is proved that the LP relaxation of bin packing, which was solved efficiently in practice by Gilmore and Gomory, has membership in P, despite the fact that it has an astronomically large number of variables. Expand

NP is as easy as detecting unique solutions

- Computer Science, Mathematics
- STOC '85
- 1985

It is shown that the problems of distinguishing between instances of SAT having zero or one solution, or finding solutions to instances of SOTA having unique solutions, are as hard as SAT itself. Expand

The NP-Completeness Column: An Ongoing Guide

- Mathematics, Computer Science
- J. Algorithms
- 1986

This is the fourteenth edition of a quarterly column that provides continuing coverage of new developments in the theory of NP-completeness, and readers who have results they would like mentioned (NP-hardness, PSPACE- hardness, polynomialtime-solvability, etc.), or open problems they wouldlike publicized, should send them to David S. Johnson. Expand

Computers and Intractability: A Guide to the Theory of NP-Completeness

- Computer Science, Mathematics
- 1978

Horn formulae play a prominent role in artificial intelligence and logic programming. In this paper we investigate the problem of optimal compression of propositional Horn production rule knowledge… Expand

On Isomorphisms and Density of NP and Other Complete Sets

- Mathematics, Computer Science
- SIAM J. Comput.
- 1977

It is shown that complete sets in EXPTIME and EXPTAPE cannot be sparse and therefore they cannot be over a single letter alphabet, and the hardest context-sensitive languages can be sparse. Expand

The complexity of theorem-proving procedures

- Computer Science, Mathematics
- STOC
- 1971

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a… Expand

The Polynomial-Time Hierarchy

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1976

The problem of deciding validity in the theory of equality is shown to be complete in polynomial-space, and close upper and lower bounds on the space complexity of this problem are established. Expand

The Design and Analysis of Computer Algorithms

- Computer Science
- 1974

This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs. Expand