Què defineix un problema difícil? Tenint en compte la pregunta anterior, escriu un context que conté la resposta. Pot ser de 1 a 20 frases. Context:
Això motiva el concepte d'un problema difícil per a una classe de complexitat. Un problema X és difícil per a una classe de problemes C si cada problema en C pot ser reduït a X. Així, cap problema en C és més difícil que X, ja que un algoritme per a X ens permet resoldre qualsevol problema en C. Per descomptat, la noció de problemes difícils depèn del tipus de reducció que s'utilitzi. Per a classes de complexitat més grans que P, es fan servir habitualment reduccions en temps polinòmic. En particular, el conjunt de problemes que són difícils per a NP és el conjunt de problemes NP-difícils.