NP-fullständighet
NP-fullständighet, egenskap hos ett antal typer av matematiska problem som med nu kända metoder kan lösas bara med ett beräkningsarbete av en omfattning som är en exponentiell funktion av problemets storlek. Ett känt exempel är handelsresandeproblemet. NP står för nondeterministic polynomial
(41 av 290 ord)
Vill du få tillgång till hela artikeln?
Medverkande
Litteraturanvisning
M.R.Garey & D.S.Johnson,
Computers and Intractability (
1979).
Källangivelse
Nationalencyklopedin,
NP-fullständighet.
http://www.ne.se/uppslagsverk/encyklopedi/lång/np-fullständighet