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:

    “Then the justice,
    In fair round belly with good capon lined,
    With eyes severe and beard of formal cut,
    Full of wise saws and modern instances;
    And so he plays his part.”
    —William Shakespeare (1564–1616)

    “Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
    —The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)