P, NP, Co-NP and weak systems of arithmetic
From MaRDI portal
Publication:672742
DOI10.1016/0304-3975(95)00099-2zbMath0873.03038MaRDI QIDQ672742
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(95)00099-2
nonstandard models of arithmetic; complexity classes; language of arithmetic; polynomial time computations; weak systems of arithmetic
03D15: Complexity of computation (including implicit computational complexity)
03F30: First-order arithmetic and fragments
03H15: Nonstandard models of arithmetic
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- \(\text{NP}\not={co}\)-NP and models of arithmetic
- Non-standard models of Peano arithmetic
- NP-complete decision problems for binary quadratics
- Nondeterministic polynomial-time computations and models of arithmetic
- On models of arithmetic—Answers to two problems raised by H. Gaifman
- Completeness Theorems, Incompleteness Theorems and Models of Arithmetic
- Existence and feasibility in arithmetic
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item