NP-komplett
From Wikipedia, the free encyclopedia
Remove ads
NP-komplett er eit omgrep innan matematikken som står for «Non-Polynomial in Time Complete». NP-komplette problem er dei problema i NP som det er «vanskelegast» å finne effektive algoritmar for. Viss ein finn ein algoritme med polynomisk køyretid for eit NP-komplett problem, tyder det at alle problem i NP kan løysast med algoritmar med polynomisk køyretid, det vil seie at P=NP. Det er ikkje kjent om det er mogleg.
Dersom eit NP-komplett problem skal løysast analytisk, må det som regel nyttast ein algoritme der køyretida aukar eksponensielt med lengda til inndataet.
 |
Remove ads
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads