On the complexity of unique solutions

DOI10.1145/62.322435zbMath0631.68038OpenAlexW2071367694MaRDI QIDQ3768398

Christos H. Papdimitriou

Publication date: 1984

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/62.322435

zbMATH Keywords

traveling salesman problempolynomial hierarchycomplete problemsuniquely optimal solution

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Related Items (28)

Simple characterizations of \(P(\# P)\) and complete problems ⋮ Efficient timed model checking for discrete-time systems ⋮ On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P ⋮ Characteristic function games with restricted agent interactions: core-stability and coalition structures ⋮ A note on complete problems for complexity classes ⋮ The unique Horn-satisfiability problem and quadratic Boolean equations. ⋮ Geometric optimization and \(D^ P\)-completeness ⋮ The complexity of optimization problems ⋮ More complicated questions about maxima and minima, and some closures of NP ⋮ Nondeterministic bounded query reducibilities ⋮ Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP ⋮ On the Complexity of Master Problems ⋮ The complexity of comparing optimal solutions ⋮ Some rainbow problems in graphs have complexity equivalent to satisfiability problems ⋮ Unnamed Item ⋮ Classifying the computational complexity of problems ⋮ \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP] ⋮ Uniqueness in quadratic and hyperbolic \(0-1\) programming problems ⋮ \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ Two hardness results for Gamson's game ⋮ Exploiting Packing Components in General-Purpose Integer Programming Solvers ⋮ Deciding uniqueness in norm maximazation ⋮ Improving known solutions is hard ⋮ The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks ⋮ Unnamed Item ⋮ Cook reducibility is faster than Karp reducibility in NP ⋮ Before and after vacuity

This page was built for publication: On the complexity of unique solutions