On the complexity of unique solutions
- 1 November 1982
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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