On Independence of Variants of the Weak Pigeonhole Principle

DOI10.1093/logcom/exm017zbMath1132.03029OpenAlexW2109248502MaRDI QIDQ5431613

Emil Jeřábek

Publication date: 12 December 2007

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/8352008c0adb73e8f8b52ed9e8572d16c79f9420

zbMATH Keywords

bounded arithmeticBoolean circuitpigeonhole principleKPT witnessing

Mathematics Subject Classification ID

Cryptography (94A60) First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)

Related Items (9)

FRAGMENTS OF APPROXIMATE COUNTING ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ The polynomial and linear hierarchies in models where the weak pigeonhole principle fails ⋮ Integer factoring and modular square roots ⋮ A note on the Σ₁collection scheme and fragments of bounded arithmetic ⋮ Abelian groups and quadratic residues in weak arithmetic ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Random resolution refutations ⋮ Approximate counting by hashing in bounded arithmetic

This page was built for publication: On Independence of Variants of the Weak Pigeonhole Principle