NP-Schwere

Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Sei <math>L_1 \sub \Sigma^*</math> also eine formale Sprache .

<math>L_1</math> heißt nun NP-schwer ( denglisch NP-hart ) falls <math>\forall L \in NP : \le_P L_1</math> also alle <math>L</math> aus NP polynomial reduzierbar auf <math>L_1</math> sind.

Siehe auch

NP-Vollständigkeit

Bücher zum Thema NP-Schwere

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/NP-Schwere.html">NP-Schwere </a>