P Versus NP Problem - Formal Definition For NP-completeness

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:

  1. ; and
  2. any is polynomial-time-reducible to (written as ), where if, and only if, the following two conditions are satisfied:
    1. There exists such that \forall w\in\Sigma^{*}(w\in L^{'}\Leftrightarrow f(w)\in L); and
    2. there exists a polynomial-time Turing machine that halts with on its tape on any input .

Read more about this topic:  P Versus NP Problem

Famous quotes containing the words formal and/or definition:

    “Two clergymen disputing whether ordination would be valid without the imposition of both hands, the more formal one said, “Do you think the Holy Dove could fly down with only one wing?””
    —Horace Walpole (1717–1797)

    “One definition of man is “an intelligence served by organs.””
    —Ralph Waldo Emerson (1803–1882)