\(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly

DOI10.1007/s10958-005-0355-0zbMath1145.03337OpenAlexW1968752321MaRDI QIDQ937909

B. E. Eshmatov

Publication date: 18 August 2008

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-005-0355-0

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structure and definability in general bounded arithmetic theories
• An arithmetical characterization of NP
• Classical recursion theory. Vol. II
• On the bounded version of Hilbert's tenth problem
• Multifunction algebras and the provability of \(PH\downarrow\)
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• Existence and feasibility in arithmetic

This page was built for publication: \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly