Hilbert's tenth problem

Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm which, for any given Diophantine equation (a polynomial equation with integer coefficients and a finite number of unknowns), can decide whether the equation has a solution with all unknowns taking integer values. For example, the Diophantine equation has an integer solution: . By contrast, the Diophantine equation has no such solution. Hilbert's tenth problem has been solved, and it has a negative answer: such a general algorithm cannot exist. This is the result of combined work of Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson which spans 21 years, with Matiyasevich completing the theorem in 1970. The theorem is now known as Matiyasevich's theorem or the MRDP theorem (an initialism for the surnames of the four principal contributors to its solution). When all coefficients and variables are restricted to be positive integers, the related problem of polynomial identity testing becomes a decidable (exponentiation-free) variation of Tarski's high school algebra problem, sometimes denoted Hilbert formulated the problem as follows: Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers. The words "process" and "finite number of operations" have been taken to mean that Hilbert was asking for an algorithm. The term "rational integral" simply refers to the integers, positive, negative or zero: 0, ±1, ±2, ... . So Hilbert was asking for a general algorithm to decide whether a given polynomial Diophantine equation with integer coefficients has a solution in integers. Hilbert's problem is not concerned with finding the solutions. It only asks whether, in general, we can decide whether one or more solutions exist.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (15)

Related people (3)

Related units (2)

Related concepts (16)

Related courses (1)

Related lectures (5)

Complex Representation Learning with Graph Convolutional Networks for Knowledge Graph Alignment

Thanh Trung Huynh, Quoc Viet Hung Nguyen, Thành Tâm Nguyên

The task of discovering equivalent entities in knowledge graphs (KGs), so-called KG entity alignment, has drawn much attention to overcome the incompleteness problem of KGs. The majority of existing techniques learns the pointwise representations of entiti ...

London2023

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem

Mika Tapani Göös

We study the search problem class PPA_q defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p. ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2020

A Local Law for Singular Values from Diophantine Equations

Marius Christopher Lemm

We introduce the

N\times N

random matrices

X_{j,k}=\exp\left(2\pi i \sum_{q=1}^d\ \omega_{j,q} k^q\right) \quad \text{with } \{\omega_{j,q}\}_{\substack{1\leq j\leq N\\ 1\leq q\leq d}} \text{ i.i.d. random variables},

and

d

a fixed integer. We pr ...

2020

In this course we will define rigorous mathematical models for computing on large datasets, cover main algorithmic techniques that have been developed for sublinear (e.g. faster than linear time) data

Diophantine set

In mathematics, a Diophantine equation is an equation of the form P(x1, ..., xj, y1, ..., yk) = 0 (usually abbreviated P(, ) = 0) where P(, ) is a polynomial with integer coefficients, where x1, ..., xj indicate parameters and y1, ..., yk indicate unknowns. A Diophantine set is a subset S of , the set of all j-tuples of natural numbers, so that for some Diophantine equation P(, ) = 0, That is, a parameter value is in the Diophantine set S if and only if the associated Diophantine equation is satisfiable under that parameter value.

Computability theory

Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory.

Formal system

A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A formal system is essentially an "axiomatic system". In 1921, David Hilbert proposed to use such a system as the foundation for the knowledge in mathematics. A formal system may represent a well-defined system of abstract thought.

Calculus of Variations MATH-604: Some Aspects of Calculus of Variations

Covers topics in Calculus of Variations, including regularity results and implicit function theorems.

Halting Problem: Unsolvable Problems CS-101: Advanced information, computation, communication I

Explores the halting problem, demonstrating its unsolvability and the limitations of algorithms.

Halting Problem: Unsolvable Problems CS-101: Advanced information, computation, communication I

Explores the unsolvability of the halting problem in algorithms and the limitations of procedures in determining program halting.