Approximate counting and NP search problems

DOI10.1142/S021906132250012XOpenAlexW2906821601MaRDI QIDQ5055313FDOQ5055313

Authors: 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

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

zbMATH Keywords

approximate countingbounded arithmeticweak pigeonhole principleswitching lemmasNP search problemsCPLS

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Existence and feasibility in arithmetic
• How easy is local search?
• On the complexity of the parity argument and other inefficient proofs of existence
• Title not available (Why is that?)
• On total functions, existence theorems and computational complexity
• The relative complexity of NP search problems
• On the weak pigeonhole principle
• The provably total search problems of bounded arithmetic
• Title not available (Why is that?)
• Title not available (Why is that?)
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Exponential lower bounds for the pigeonhole principle
• Herbrandizing search problems in Bounded Arithmetic
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Propositional proofs and reductions between NP search problems
• Approximate counting in bounded arithmetic
• Characterising definable search problems in bounded arithmetic via proof notations
• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
• NP search problems in low fragments of bounded arithmetic
• A new proof of the weak pigeonhole principle
• The provably total NP search problems of weak second order bounded arithmetic
• Witnessing functions in bounded arithmetic and search problems
• Fragments of approximate counting
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• Integer factoring and modular square roots
• Towards a unified complexity theory of total functions
• Short proofs of the Kneser-Lovász coloring principle
• A note about \(k\)-DNF resolution
• The ordering principle in a fragment of approximate counting
• Improved witnessing and local improvement principles for second-order bounded arithmetic
• Approximate counting by hashing in bounded arithmetic
• A model-theoretic characterization of the weak pigeonhole principle
• Feasibly constructive proofs of succinct weak circuit lower bounds
• Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
• Random resolution refutations
• Typical forcings, NP search problems and an extension of a theorem of Riis
• Title not available (Why is that?)
• A Characterisation of Definable NP Search Problems in Peano Arithmetic

Cited In (10)

• On the Effective Enumerability of NP Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximate counting with \(m\) counters: A detailed analysis
• Descriptive Complexity of approximate counting CSPs
• Title not available (Why is that?)
• Approximate Counting CSP Seen from the Other Side
• Title not available (Why is that?)
• 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)