The Ordering Principle in a Fragment of Approximate Counting

DOI10.1145/2629555zbMath1354.03090OpenAlexW2153365469MaRDI QIDQ2946740

Neil Thapen, Albert Atserias

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2629555

zbMATH Keywords

computational complexitybounded arithmeticpropositional proof complexitypolynomial local search

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)

Related Items (5)

Approximate counting and NP search problems ⋮ A note about \(k\)-DNF resolution ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Random resolution refutations

Cites Work

• Unnamed Item
• A model-theoretic characterization of the weak pigeonhole principle
• Approximate counting by hashing in bounded arithmetic
• Witnessing functions in bounded arithmetic and search problems
• A Note on Conservativity Relations among Bounded Arithmetic Theories

This page was built for publication: The Ordering Principle in a Fragment of Approximate Counting