NP difficile / completo

Non c'è nulla di ovvio nel determinismo e nel non-determinismo che porta a questo. È un po 'tecnico.

Un automa deterministico corrisponde a ciò che possiamo effettivamente costruire, sia nell'hardware che nel software.

Un automone non deterministico cerca tutte le soluzioni possibili, ma per essere in tempo polinomiale deve essere in grado di verificare una possibile soluzione in tempo polinomiale. Se ne avete abbastanza della teoria, riconoscerete che un NA è equivalente a un DA con un oracolo che fornisce misteriosamente una soluzione, quindi un NA può risolvere qualcosa in tempo polinomiale se un DA può verificare una soluzione proposta in tempo polinomiale. Un automa non deterministico equivale a un automa deterministico che cerca tutte le possibili combinazioni e l'insieme di tutte le possibili combinazioni ha esponenzialmente più membri dell'insieme di cose che vengono combinate, quindi se un NA può fare qualcosa in tempo polinomiale un DA può certamente farlo in esponenziale.

NP è l'insieme di problemi decisionali tale che un DA (quindi un vero computer) può verificare una soluzione in tempo polinomiale. Se non possiamo verificare una soluzione proposta in tempo polinomiale, non saremo certamente in grado di generarne uno, quindi NP è essenzialmente l'insieme di problemi decisionali che potrebbero avere soluzioni di tempo polinomiale reali.

Il Problema del commesso viaggiatore, come solitamente riportato, non è in NP perché non è chiaro come verificare che una determinata rotta sia la più economica in termini di tempo polinomiale. Tuttavia, una variante del TSP in cui la domanda è se c'è una soluzione con un costo sotto X è in NP, dal momento che è facilmente verificabile, e se siamo in grado di risolvere tale problema, possiamo determinare facilmente la rotta più economica. Pertanto, il TSP come di solito dichiarato è NP-hard, il che significa che è difficile da risolvere come un problema NP-completo.

Ci sono problemi che non hanno conosciuto soluzioni polinomiali per un NA, e problemi che sappiamo non sono in NP. Questi problemi sono solitamente classificati da ulteriori classi di complessità (i problemi di PSpace, ad esempio, possono essere risolti nello spazio polinomiale, ma possibilmente solo in termini di tempo esponenziale) o elencati come indecidibili. Non conosco alcun termine per un problema, ad esempio PSpace, ma non è noto che sia in NP.

NP prende il nome dal fatto che può essere risolto in tempo polinomiale da Macchina non deterministica . Il trucco è che in questo caso non deterministico significa, come se potesse valutare magicamente tutti i rami in parallelo. È un modello teorico, non dovresti tentare di confrontarlo con i computer della vita reale. In effetti, ha molto più a che fare con l'area della matematica nota come teoria dei linguaggi formali e della computabilità .

NDTM può essere "ridotto" alla macchina di Turing deterministica, ma in tempo esponenziale. Ecco perché non ci sono soluzioni polinomiali per problemi NP-completi sui computer, che (come hai giustamente notato) sono deterministici.

Il concetto di deterministico contro non deterministico entra in gioco dal modo in cui questi problemi vengono studiati su Turing Machines.

Concettualmente, una macchina di Turing può risolvere qualsiasi problema completo di Turing attraverso uno dei due metodi seguenti:

1. Ogni azione viene eseguita in modo sequenziale senza ramificazioni quando viene presa una decisione, cioè deterministica in quanto puoi seguire da solo il percorso esatto dell'esecuzione.
2. Ogni azione viene eseguita in sequenza ma un ramo si verifica quando viene presa una decisione in modo che ogni ramo possa essere esplorato, cioè una macchina di Turing non deterministica.

Quindi, su una macchina non deterministica, se l'algoritmo può trovare una soluzione, si sa che esiste una soluzione trovata in tempo polinomiale, ma non sai quale ramo di esecuzione è stato utilizzato per trovare quella soluzione. Le cose si fanno interessanti perché una macchina di Turing può simulare una macchina di Turing non deterministica, ma per fare ciò deve calcolare ogni percorso attraverso il codice e questo è dove la natura esponenziale dei problemi di NP.

Le macchine di Turing sono utilizzate per questo tipo di studio a causa della loro natura semplice che rende molto più facile la loro comprensione a livello matematico quando si è preoccupati della matematica di base del problema senza doversi preoccupare del sovraccarico che potrebbe essere coinvolto con utilizzando diversi tipi di macchine.

Riguardo a un problema per il quale abbiamo una soluzione esponenziale su una macchina deterministica di Turing ma nessuna riduzione a un problema noto, sarebbe EXPTIME .