On the complexity of finding falsifying assignments for Herbrand disjunctions

DOI10.1007/s00153-015-0439-6zbMath1378.03043arXiv1411.3304OpenAlexW1530232604MaRDI QIDQ892133

Pavel Pudlák

Publication date: 18 November 2015

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.3304

zbMATH Keywords

falsifying assignmentHerbrand theorempolynomial search problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (7)

TFNP: An Update ⋮ NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Towards a unified complexity theory of total functions ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\)

Cites Work

• How easy is local search?
• The provably total search problems of bounded arithmetic
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Logical Foundations of Mathematics and Computational Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of finding falsifying assignments for Herbrand disjunctions