Formal Definition For NP-completeness
There are many equivalent ways of describing NP-completeness.
Let be a language over a finite alphabet .
is NP-complete if, and only if, the following two conditions are satisfied:
- ; and
- any is polynomial-time-reducible to (written as ), where if, and only if, the following two conditions are satisfied:
- There exists such that
; and
- there exists a polynomial-time Turing machine that halts with on its tape on any input .
- There exists such that
Read more about this topic: P Versus NP Problem
Famous quotes containing the words formal and/or definition:
“The bed is now as public as the dinner table and governed by the same rules of formal confrontation.”
—Angela Carter (19401992)
“The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
—Samuel Taylor Coleridge (17721834)