Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: NP-hart, NP-vollständig Aufwärts: NPC Beweise Vorherige Seite: Die große Frage der   Inhalt

Polynomielle Reduzierbarkeit

$L$ heißt auf $K$ polynomiell reduzierbar, wenn es eine total berechenbare Funktion $f$ gibt, so daß gilt
  • $x\in L \Leftrightarrow f(x)\in K$
  • $f$ ist in polynomieller Zeit berechenbar.