Approximate counting and NP search problems
DOI10.1142/S021906132250012XOpenAlexW2906821601MaRDI QIDQ5055313
Neil Thapen, Leszek Aleksander Kołodziejczyk
Publication date: 13 December 2022
Published in: Journal of Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1812.10771
bounded arithmeticapproximate countingweak pigeonhole principleswitching lemmasNP search problemsCPLS
Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) 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)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Propositional proofs and reductions between NP search problems
- The provably total NP search problems of weak second order bounded arithmetic
- Exponential lower bounds for the pigeonhole principle
- Alternating minima and maxima, Nash equilibria and bounded arithmetic
- On total functions, existence theorems and computational complexity
- Integer factoring and modular square roots
- How easy is local search?
- The relative complexity of NP search problems
- On the complexity of the parity argument and other inefficient proofs of existence
- Short proofs of the Kneser-Lovász coloring principle
- A note about \(k\)-DNF resolution
- Towards a unified complexity theory of total functions
- A model-theoretic characterization of the weak pigeonhole principle
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Random resolution refutations
- Typical forcings, NP search problems and an extension of a theorem of Riis
- On the weak pigeonhole principle
- FRAGMENTS OF APPROXIMATE COUNTING
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- The Ordering Principle in a Fragment of Approximate Counting
- The provably total search problems of bounded arithmetic
- Herbrandizing search problems in Bounded Arithmetic
- Approximate counting by hashing in bounded arithmetic
- POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
- A Characterisation of Definable NP Search Problems in Peano Arithmetic
- Witnessing functions in bounded arithmetic and search problems
- 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
- NP search problems in low fragments of bounded arithmetic
- Improved witnessing and local improvement principles for second-order bounded arithmetic
- Approximate counting in bounded arithmetic
- Existence and feasibility in arithmetic
- A new proof of the weak pigeonhole principle
This page was built for publication: Approximate counting and NP search problems
