Hvað skilgreinir erfitt vandamál? Skrifaðu svarið í samhengi við fyrri spurningu. Það geta verið 1 - 20 setningar. Umfjöllun:
Þetta hvetur hugtakið um vandamál sem er erfitt fyrir flókið flokk. Vandamál X er erfitt fyrir flokki vandamála C ef hægt er að minnka hvert vandamál í C niður í X. Þannig er ekkert vandamál í C erfiðara en X, þar sem algoritmi fyrir X gerir okkur kleift að leysa hvaða vandamál sem er í C. Auðvitað fer hugtakið erfitt vandamál eftir tegund minnkunar sem er notuð. Fyrir flókið flokkum stærri en P, fjölnefna-tíma minnkanir eru venjulega notuð. Sérstaklega er fjöldi vandamála sem eru erfiðir fyrir NP fjöldi NP-erfiða vandamála.