The consequences of eliminating NP solutions
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1332676 (Why is no real title available?)
- scientific article; zbMATH DE number 2000818 (Why is no real title available?)
- scientific article; zbMATH DE number 1926632 (Why is no real title available?)
- scientific article; zbMATH DE number 3799016 (Why is no real title available?)
- scientific article; zbMATH DE number 1414291 (Why is no real title available?)
- scientific article; zbMATH DE number 5018174 (Why is no real title available?)
- #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
- A Richer Understanding of the Complexity of Election Systems
- A Short Introduction to Computational Social Choice
- A complexity theory for feasible closure properties
- A hierarchy based on output multiplicity
- A note on SpanP functions
- A taxonomy of complexity classes of functions
- Average-case intractability vs. worst-case intractability
- Closure properties and witness reduction
- Cluster computing and the power of edge recognition
- Communication complexity of key agreement on small ranges
- Competing provers yield improved Karp-Lipton collapse results
- Computable queries for relational data bases
- Computational Complexity of Probabilistic Turing Machines
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- False-name manipulations in weighted voting games
- Functions computable with limited access to NP
- Functions computable with nonadaptive queries to NP
- Gap-definable counting classes
- Matching is as easy as matrix inversion
- Mathematical Properties of the Banzhaf Power Index
- More on BPP and the polynomial-time hierarchy
- NP is as easy as detecting unique solutions
- NP-completeness for calculating power indices of weighted majority games
- NP-completeness of some problems concerning voting games
- On closure properties of \(\#\text{P}\) in the context of \(\text{PF} \circ \#\text{P}\)
- On counting and approximation
- On self-reducibility and weak P-selectivity
- On the Structure of Polynomial Time Reducibility
- On the autoreducibility of functions
- On the closure of certain function classes under integer division by polynomially-bounded functions
- On the construction of parallel computers from various basis of Boolean functions
- On the hardness of approximate reasoning
- PP is closed under truth-table reductions
- Polynomial Time Enumeration Reducibility
- Quantitative Relativizations of Complexity Classes
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- Reducing the number of solutions of NP functions
- Reductions between disjoint NP-pairs
- Relative complexity of checking and evaluating
- Strong nondeterministic polynomial-time reducibilities
- Survey propagation: An algorithm for satisfiability
- Symmetric alternation captures BPP
- The Complexity of Computing the Size of an Interval
- The Complexity of Enumeration and Reliability Problems
- The Complexity of Power-Index Comparison
- The complexity of combinatorial problems with succinct input representation
- The complexity of computing the permanent
- The complexity of optimization problems
- The complexity theory companion
- The polynomial-time hierarchy
- Theory of semi-feasible algorithms
- Threshold Computation and Cryptographic Security
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)
