The consequences of eliminating NP solutions
From MaRDI portal
Publication:458458
DOI10.1016/j.cosrev.2008.02.001zbMath1302.68124OpenAlexW1979759083MaRDI QIDQ458458
Piotr Faliszewski, Hemaspaandra, Lane A.
Publication date: 7 October 2014
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1802/3452
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Average-case intractability vs. worst-case intractability
- The complexity of computing the permanent
- NP-completeness of some problems concerning voting games
- On the autoreducibility of functions
- On self-reducibility and weak P-selectivity
- Strong nondeterministic polynomial-time reducibilities
- On the construction of parallel computers from various basis of Boolean functions
- NP is as easy as detecting unique solutions
- The complexity of combinatorial problems with succinct input representation
- Matching is as easy as matrix inversion
- The complexity of optimization problems
- On counting and approximation
- Computable queries for relational data bases
- On the closure of certain function classes under integer division by polynomially-bounded functions
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- Symmetric alternation captures BPP
- A hierarchy based on output multiplicity
- Gap-definable counting classes
- A note on SpanP functions
- A taxonomy of complexity classes of functions
- Functions computable with limited access to NP
- More on BPP and the polynomial-time hierarchy
- Functions computable with nonadaptive queries to NP
- Reducing the number of solutions of NP functions
- Competing provers yield improved Karp-Lipton collapse results
- On closure properties of \(\#\text{P}\) in the context of \(\text{PF} \circ \#\text{P}\)
- Closure properties and witness reduction
- PP is closed under truth-table reductions
- A complexity theory for feasible closure properties
- Reductions between disjoint NP-pairs
- Cluster computing and the power of edge recognition
- On the hardness of approximate reasoning
- False-Name Manipulations in Weighted Voting Games
- The Complexity of Power-Index Comparison
- Quantitative Relativizations of Complexity Classes
- The Complexity of Enumeration and Reliability Problems
- #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
- On the Structure of Polynomial Time Reducibility
- Computational Complexity of Probabilistic Turing Machines
- Polynomial Time Enumeration Reducibility
- Mathematical Properties of the Banzhaf Power Index
- Threshold Computation and Cryptographic Security
- Communication complexity of key agreement on small ranges
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- A Richer Understanding of the Complexity of Election Systems
- Survey propagation: An algorithm for satisfiability
- The Complexity of Computing the Size of an Interval
- A Short Introduction to Computational Social Choice
- The complexity theory companion
- NP-completeness for calculating power indices of weighted majority games
- Theory of semi-feasible algorithms
This page was built for publication: The consequences of eliminating NP solutions
