Ciò che significa intrattabilità nella pratica è aperto al dibattito. Dire che un problema non è presente in P non significa che tutti i grandi casi del problema siano duri o addirittura che la maggior parte di essi lo siano. Ad esempio, è stato dimostrato che il problema di decisione nell' aritmetica Presburger non è presente in P, eppure sono stati scritti algoritmi che risolvono il problema in tempi ragionevoli nella maggior parte dei casi. Allo stesso modo, gli algoritmi possono risolvere il problema dello zaino completo NP su un' ampia gamma di dimensioni in meno di tempo quadratico e i solutori SAT gestiscono di routine le istanze di grandi dimensioni del problema di soddisfazione booleana completa NP.
Nonostante il problema di Presburger e a causa dell' intrattabilità, cosa è stato fatto per trovare soluzioni in tempi ragionevoli?
sono stati scritti algoritmi sono stati scritti algoritmi sono stati scritti algoritmi che risolvono il problema in tempi ragionevoli nella maggior parte dei casi