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 classesDiophantine setsMatiyasevich-Robinson-Davis-Putnam theoremproof complexityweak fragments of arithmeticweak reductions

Mathematics Subject Classification ID

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

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)

• Diophantine hierarchy
• The weak pigeonhole principle for function classes inS12
• A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• Removing the strong RSA assumption from arguments over the integers
• Further results on Hilbert's tenth problem
• \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly

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)