Editing P versus NP problem (section)

===NP-completeness===
{{Main|NP-completeness}}

There are many equivalent ways of describing NP-completeness.

Let ''L'' be a language over a finite alphabet Σ.

''L'' is NP-complete if, and only if, the following two conditions are satisfied:

# ''L'' ∈ NP; and
# any ''L&prime;'' in NP is polynomial-time-reducible to ''L'' (written as <math>L' \leq_{p} L</math>), where <math>L' \leq_{p} L</math> if, and only if, the following two conditions are satisfied:
## There exists ''f'' : Σ* → Σ* such that for all ''w'' in Σ* we have: <math>(w\in L' \Leftrightarrow f(w)\in L)</math>; and
## there exists a polynomial-time Turing machine that halts with ''f''(''w'') on its tape on any input ''w''.

Alternatively, if ''L'' ∈ NP, and there is another NP-complete problem that can be polynomial-time reduced to ''L'', then ''L'' is NP-complete. This is a common way of proving some new problem is NP-complete.