On the complexity of unique solutions
- 1 November 1982
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 14-20
- https://doi.org/10.1109/sfcs.1982.28
Abstract
We show that the problem of deciding whether an instance of the traveling salesman problem has a uniquely optimal solution is complete for Δ2P.Keywords
This publication has 7 references indexed in Scilit:
- The complexity of facets (and some facets of complexity)Published by Association for Computing Machinery (ACM) ,1982
- Flowshop scheduling with limited temporary storageJournal of the ACM, 1980
- The adjacency relation on the traveling salesman polytope is NP-CompleteMathematical Programming, 1978
- The Planar Hamiltonian Circuit Problem is NP-CompleteSIAM Journal on Computing, 1976
- Word problems requiring exponential time(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1973
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971