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.

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.

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.
Q908207
complexiteitsgraad
Concept
Q3262192
beslissingsprobleem
Concept
Q628036
NP
MISC
Q628036
NP
MISC
Q215206
NP-volledig
MISC
Q875276
MAX-SAT
Concept
Q322212
handelsreizigersprobleem
Concept
None
EXPTIME-volledig
UNK
Stop-probleem
UNK
None
Geheeltallig lineair programmeren
UNK
Q1137554
NP-moeilijk
MISC
Q1137554
NP-moeilijk
MISC
Q1137554
NP-moeilijk
MISC
Q1137554
NP-moeilijk
MISC
Q1137554
NP-moeilijk
MISC
Q1137554
NP-moeilijk
MISC
Q1137554
NP-moeilijk
MISC
instance of
part of