On the complexity of unique solutions

DOI10.1145/62.322435MaRDI QIDQ3768398zbMATH OpenOpenAlexFDO

Authors 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

complete problemspolynomial hierarchytraveling salesman problemuniquely optimal solution

Mathematics Subject Classification ID

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

Cited in

(33)

• Before and after vacuity
• NP is as easy as detecting unique solutions
• A note on complete problems for complexity classes
• 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
• \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
• Simple characterizations of \(P(\# P)\) and complete problems
• The unique Horn-satisfiability problem and quadratic Boolean equations.
• Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
• Efficient timed model checking for discrete-time systems
• Uniqueness in quadratic and hyperbolic \(0-1\) programming problems
• Characteristic function games with restricted agent interactions: core-stability and coalition structures
• The complexity of comparing optimal solutions
• On the breakdown of uniqueness of the solution
• On the complexity of master problems
• The complexity of finding \(k\)th most probable explanations in probabilistic networks
• scientific article; zbMATH DE number 4169980 (Why is no real title available?)
• Classifying the computational complexity of problems
• Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
• Exploiting packing components in general-purpose integer programming solvers
• scientific article; zbMATH DE number 809154 (Why is no real title available?)
• Two hardness results for Gamson's game
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy
• Equilibrium design for concurrent games
• Some rainbow problems in graphs have complexity equivalent to satisfiability problems
• Deciding uniqueness in norm maximazation
• Improving known solutions is hard
• Designing equilibria in concurrent games with social welfare and temporal logic constraints
• Cook reducibility is faster than Karp reducibility in NP
• On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3768398)