Revision #869 → #1433 · back to history
addedNP-hard (informal)a7379d22b4d5
addedSubset sum is NP-hard1d980f0e45d4
addedNP-hard at least as difficult as NPdd5fd20e1a23
addedNP-hard via many-one reduction7586e4b97b8c
addedNP-hard via NP-complete reduction79e1a62f1ee7
addedNP-hard not in P if P≠NP714f14add180
addedApproximability of NP-hard optimization5d08a5072fea
addedNP-complete problems are NP-hard159c4398a46a
addedTravelling salesman is NP-hard5a0066d3dad5
addedSubset sum decision probleme838faf8e262
addedHalting problem is NP-hard not NP-complete2397ba1bb682
addedTrue quantified Boolean formulasa9c8d1035e88
addedNP class41f3b3b7198e
addedNP-hard class9bbfecbbcc2c
addedNP-complete classfd7a58faf052
addedNP-easy class4f39f84b7053
addedNP-equivalent class3ad589996210
addedNP-intermediate existencee08d6c4392af