Approximate counting and NP search problems
From MaRDI portal
approximate countingbounded arithmeticCPLSNP search problemsswitching lemmasweak pigeonhole principle
Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
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
- 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
- Consistency of circuit lower bounds with bounded theories
- 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?
- 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 3305097 (Why is no real title available?)
- 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
(12)- scientific article; zbMATH DE number 1670534 (Why is no real title available?)
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Descriptive Complexity of approximate counting CSPs
- On the Effective Enumerability of NP Problems
- Approximate counting with m counters: A detailed analysis
- scientific article; zbMATH DE number 1979521 (Why is no real title available?)
- Approximate Counting CSP Seen from the Other Side
- Fine-Grained Reductions from Approximate Counting to Decision
- scientific article; zbMATH DE number 7561704 (Why is no real title available?)
- scientific article; zbMATH DE number 6297698 (Why is no real title available?)
- Polynomial calculus space and resolution width
- TFNP intersections through the Lens of feasible disjunction
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)
