CONSISTENCY OF CIRCUIT EVALUATION, EXTENDED RESOLUTION AND TOTAL NP SEARCH PROBLEMS

DOI10.1017/fms.2016.13zbMath1402.03082arXiv1509.03048OpenAlexW2222642079MaRDI QIDQ5739904

Jan Krajíček

Publication date: 6 July 2016

Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)

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

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (1)

Towards a unified complexity theory of total functions

Cites Work

• Unnamed Item
• The provably total NP search problems of weak second order bounded arithmetic
• Exponentiation and second-order bounded arithmetic
• The relative complexity of NP search problems
• On the complexity of the parity argument and other inefficient proofs of existence
• Implicit proofs

This page was built for publication: CONSISTENCY OF CIRCUIT EVALUATION, EXTENDED RESOLUTION AND TOTAL NP SEARCH PROBLEMS