NP-moeilijk

NP-moeilijk is een complexiteitsgraad. Een gegeven probleem A is NP-moeilijk als ieder beslissingsprobleem in NP in polynomiale tijd tot A gereduceerd kan worden; het is dus minstens zo moeilijk als ieder probleem in NP. Als het probleem zelf ook tot de klasse NP behoort, dan is het NP-volledig. Niet ieder probleem dat NP-moeilijk is, is NP-volledig; het omgekeerde is — per definitie — wel het geval. Voorbeelden van NP-moeilijke beslissingsproblemen zijn MAX-SAT en het handelsreizigersprobleem.

Principes

Computationele complexiteitstheorie

Modellen

Algoritme

Turingmachine

Lambdacalculus

Theorieën

Berekenbaarheid

Complexiteitsgraad

NP-volledig

Soms is het probleem in kwestie aantoonbaar moeilijker dan NP: bijvoorbeeld het vinden van de beste schaakzet in een gegeneraliseerd schaakspel op een n x n bord. Dit probleem is EXPTIME-volledig^[1].

Het Stop-probleem is zelfs onbeslisbaar. Het is dus NP-moeilijk, maar niet NP-volledig. Aan de andere kant kan het zo zijn dat het (nog) niet bekend is of het probleem in kwestie deel uitmaakt van NP. Soms is het eenvoudig om een bewijs te leveren dat een probleem NP-moeilijk is, maar is het bewijs dat het probleem deel uitmaakt van NP het lastigste deel van een NP-volledigheidsbewijs. Geheeltallig lineair programmeren is een probleem waarvan het NP-moeilijkheidsbewijs niet zo moeilijk is, maar het veel lastiger is gebleken om te bewijzen dat het probleem deel uitmaakt van NP.

Bronnen, noten en/of referenties

1. Computing a perfect strategy for n×n chess requires time exponential in n, J. Comb. Th. A, 31, 1981, pp. 199-213