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:

    “The manifestation of poetry in external life is formal perfection. True sentiment grows within, and art must represent internal phenomena externally.”
    —Franz Grillparzer (1791–1872)

    “It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
    —Jane Adams (20th century)