[elektro] Mi az az NP?

[Kovács József]

> Egy allashirdetesben lattam, hogy elony a DSP es NP ismeret.

Ha, a DSP a terület akkor az
NP = Non Polinom algoritmusok ismerete.
(nem determinisztikus Turing gép)
Igen  jó eséllyel...

KJ

"Egy problémáról akkor mondjuk, hogy NP-beli,
ha van hozzá olyan nem determinisztikus Turing-gép, amely
a gép valamelyik működése esetén polinomiális sok lépés után
1-et ír a szalagra, ha van megoldása a problémának,
ha pedig nincs, akkor ez semelyik működésnél sem fordulhat elõ.

Az NP betűk nem determinisztikusan polinomiális
kifejezésbõl származnak."

> TBS::Antiemes