Diophantine equations

From Glossary

Jump to: navigation, search

A system of equations whose variables must be integer-valued. A famous one is in Fermat's Last Theorem:

x^n + y^n = z^n.
In general, solving the linear Diophantine equations, LaTeX: Ax = b for LaTeX: x \in \mathbb{Z}^n can be solved in polynomial time. However, with bounds, LaTeX: 0 \le x \le u, the problem is NP-complete.

Personal tools