The consequences of eliminating NP solutions
DOI10.1016/J.COSREV.2008.02.001zbMATH Open1302.68124OpenAlexW1979759083MaRDI QIDQ458458FDOQ458458
Piotr Faliszewski, Lane A. Hemaspaandra
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- The complexity of optimization problems
- A taxonomy of complexity classes of functions
- The complexity of computing the permanent
- Computable queries for relational data bases
- The Complexity of Enumeration and Reliability Problems
- On the Structure of Polynomial Time Reducibility
- Title not available (Why is that?)
- A Richer Understanding of the Complexity of Election Systems
- A Short Introduction to Computational Social Choice
- On the hardness of approximate reasoning
- Mathematical Properties of the Banzhaf Power Index
- The polynomial-time hierarchy
- Computational Complexity of Probabilistic Turing Machines
- The complexity of combinatorial problems with succinct input representation
- NP is as easy as detecting unique solutions
- Matching is as easy as matrix inversion
- On self-reducibility and weak P-selectivity
- Competing provers yield improved Karp-Lipton collapse results
- False-Name Manipulations in Weighted Voting Games
- The Complexity of Power-Index Comparison
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- NP-completeness for calculating power indices of weighted majority games
- Relative complexity of checking and evaluating
- On counting and approximation
- Quantitative Relativizations of Complexity Classes
- NP-completeness of some problems concerning voting games
- #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
- Strong nondeterministic polynomial-time reducibilities
- On the construction of parallel computers from various basis of Boolean functions
- On the closure of certain function classes under integer division by polynomially-bounded functions
- Symmetric alternation captures BPP
- A hierarchy based on output multiplicity
- Gap-definable counting classes
- A note on SpanP 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
- 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
- Polynomial Time Enumeration Reducibility
- Title not available (Why is that?)
- Threshold Computation and Cryptographic Security
- Title not available (Why is that?)
- Communication complexity of key agreement on small ranges
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Survey propagation: An algorithm for satisfiability
- The Complexity of Computing the Size of an Interval
- The complexity theory companion
- Theory of semi-feasible algorithms
- Average-case intractability vs. worst-case intractability
- On the autoreducibility of functions
Cited In (3)
This page was built for publication: The consequences of eliminating NP solutions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458458)
