Per evidenziare ulteriormente la differenza tra un problema e un caso, si consideri il seguente esempio della versione di decisione del problema del venditore viaggiante: c' è un percorso di oltre 2000 chilometri che attraversa tutte le 15 città più grandi della Germania? La risposta quantitativa a questo particolare caso di problema è poco utile per risolvere altri casi del problema, come la richiesta di un viaggio di andata e ritorno in tutti i siti di Milano la cui lunghezza totale è al massimo di 10 km. Per questo motivo, la teoria della complessità affronta problemi computazionali e non casi particolari.
Da quanti chilometri il problema del venditore viaggiante cerca di classificare un percorso tra le 15 città più grandi della Germania?
2000 2000 2000