I problemi che possono essere risolti in teoria (ad esempio, dato il tempo ampio ma limitato), ma che in pratica richiedono troppo tempo prima che le loro soluzioni siano utili, sono noti come problemi intrattabili. Nella teoria della complessità, i problemi che mancano di soluzioni polinomiali sono considerati intrattabili per più dei più piccoli input. Infatti, la tesi di Cobham-Edmonds afferma che solo quei problemi che possono essere risolti nel tempo polinomio possono essere calcolati facilmente su qualche dispositivo computazionale. I problemi che sono noti per essere intrattabili in questo senso includono quelli che sono EXPTIME-hard. Se NP non è uguale a P, allora anche i problemi di NP-completa sono intrattabili in questo senso. Per vedere perchè gli algoritmi in tempo esponenziale potrebbero essere inutilizzabili nella pratica, considerare un programma che fa operazioni da 2n prima di fermarsi. Per piccoli n, diciamo 100, e supponendo per il bene di esempio che il computer fa 1012 operazioni ogni secondo, il programma sarebbe eseguito per circa 4 × 1010 anni, che è lo stesso ordine di grandezza come l' età dell' universo. Anche con un computer molto più veloce, il programma sarebbe utile solo per casi molto piccoli e in questo senso l' intrattabilità di un problema è un po' indipendente dal progresso tecnologico. Tuttavia, un algoritmo del tempo polinomio non è sempre pratico. Se il suo tempo di esecuzione è, per esempio, n.15, è irragionevole considerarlo efficiente ed è ancora inutile se non in piccoli casi.
Problemi in grado di soluzioni teoriche ma che richiedono un tempo irragionevole nell' applicazione pratica sono noti come cosa?
problemi intrattabili problemi intrattabili