On the complexity of finding falsifying assignments for Herbrand disjunctions
From MaRDI portal
Publication:892133
DOI10.1007/s00153-015-0439-6zbMath1378.03043arXiv1411.3304OpenAlexW1530232604MaRDI QIDQ892133
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
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
This page was built for publication: On the complexity of finding falsifying assignments for Herbrand disjunctions