On the bounded version of Hilbert's tenth problem

DOI10.1007/s00153-002-0162-yzbMath1026.03042OpenAlexW2020594375MaRDI QIDQ1407606

Chris Pollett

Publication date: 16 September 2003

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

Full work available at URL: https://doi.org/10.1007/s00153-002-0162-y

zbMATH Keywords

proof complexitycomplexity classesDiophantine setsweak fragments of arithmeticMatiyasevich-Robinson-Davis-Putnam theoremweak reductions

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (5)

Diophantine hierarchy ⋮ \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly ⋮ Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ Removing the Strong RSA Assumption from Arguments over the Integers ⋮ The weak pigeonhole principle for function classes inS12

This page was built for publication: On the bounded version of Hilbert's tenth problem