On the bounded version of Hilbert's tenth problem

DOI10.1007/S00153-002-0162-YMaRDI QIDQ1407606zbMATH OpenOpenAlexFDO

Authors 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

complexity classesproof complexityDiophantine setsweak fragments of arithmeticMatiyasevich-Robinson-Davis-Putnam theoremweak reductions

Mathematics Subject Classification ID

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

Recommendations

• Hilbert's tenth problem for weak theories of arithmetic
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• On the provability logic of bounded arithmetic
• scientific article; zbMATH DE number 999649
• scientific article; zbMATH DE number 1070621

Cited in

(7)

• Further results on Hilbert's tenth problem
• The weak pigeonhole principle for function classes inS12
• Diophantine hierarchy
• A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
• \(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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1407606)