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:

    “It is in the nature of allegory, as opposed to symbolism, to beg the question of absolute reality. The allegorist avails himself of a formal correspondence between “ideas” and “things,” both of which he assumes as given; he need not inquire whether either sphere is “real” or whether, in the final analysis, reality consists in their interaction.”
    —Charles, Jr. Feidelson, U.S. educator, critic. Symbolism and American Literature, ch. 1, University of Chicago Press (1953)

    “No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
    —Florence Nightingale (1820–1910)