Approximate counting and NP search problems
From MaRDI portal
Publication:5055313
approximate countingbounded arithmeticweak pigeonhole principleswitching lemmasNP search problemsCPLS
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15)
Recommendations
- The relative complexity of approximate counting problems
- scientific article; zbMATH DE number 1670534
- scientific article; zbMATH DE number 1979521
- On the parameterized complexity of approximate counting
- Counting problems in parameterized complexity
- scientific article; zbMATH DE number 1775419
- The Parameterized Complexity of Counting Problems
- Approximation algorithms for NP-hard problems
- Randomized Approximations of Parameterized Counting Problems
- Descriptive Complexity of approximate counting CSPs
Cites work
- scientific article; zbMATH DE number 3912375 (Why is no real title available?)
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 65749 (Why is no real title available?)
- scientific article; zbMATH DE number 3557241 (Why is no real title available?)
- scientific article; zbMATH DE number 512985 (Why is no real title available?)
- scientific article; zbMATH DE number 7215291 (Why is no real title available?)
- scientific article; zbMATH DE number 3305097 (Why is no real title available?)
- A Characterisation of Definable NP Search Problems in Peano Arithmetic
- A model-theoretic characterization of the weak pigeonhole principle
- A new proof of the weak pigeonhole principle
- A note about k-DNF resolution
- Alternating minima and maxima, Nash equilibria and bounded arithmetic
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Approximate counting by hashing in bounded arithmetic
- Approximate counting in bounded arithmetic
- Characterising definable search problems in bounded arithmetic via proof notations
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Existence and feasibility in arithmetic
- Exponential lower bounds for the pigeonhole principle
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Fragments of approximate counting
- Herbrandizing search problems in Bounded Arithmetic
- How easy is local search?
- Improved witnessing and local improvement principles for second-order bounded arithmetic
- Integer factoring and modular square roots
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- NP search problems in low fragments of bounded arithmetic
- On the complexity of the parity argument and other inefficient proofs of existence
- On the weak pigeonhole principle
- On total functions, existence theorems and computational complexity
- Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
- Propositional proofs and reductions between NP search problems
- Random resolution refutations
- Short proofs of the Kneser-Lovász coloring principle
- The ordering principle in a fragment of approximate counting
- The provably total NP search problems of weak second order bounded arithmetic
- The provably total search problems of bounded arithmetic
- The relative complexity of NP search problems
- Towards a unified complexity theory of total functions
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Witnessing functions in bounded arithmetic and search problems
Cited in
(10)- On the Effective Enumerability of NP Problems
- scientific article; zbMATH DE number 1670534 (Why is no real title available?)
- scientific article; zbMATH DE number 1979521 (Why is no real title available?)
- Approximate counting with m counters: A detailed analysis
- Descriptive Complexity of approximate counting CSPs
- Approximate Counting CSP Seen from the Other Side
- scientific article; zbMATH DE number 6297698 (Why is no real title available?)
- scientific article; zbMATH DE number 7561704 (Why is no real title available?)
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Fine-Grained Reductions from Approximate Counting to Decision
This page was built for publication: Approximate counting and NP search problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5055313)
