Perché i problemi NP chiamati in questo modo (e NP-hard e NP-completo)?

Question

Davvero .. Sto avendo l'ultimo test per la laurea questo Martedì, e questo è una delle cose che ho appena non riuscivo a capire. Mi rendo conto che una soluzione per il problema NP può essere verfied in tempo polinomiale. Ma che cosa fa il determinismo ha a che fare con questo?
E se si potesse spiegarmi dove NP-completi e NP-hard ha ottenuto i loro nomi, che sarebbe grande (sono abbastanza sicuro di ottenere il significato di loro, io non vedere ciò che i loro nomi hanno a che fare con quello che sono).
Scusate se questo è banale, non riesco proprio a sembrare convincerlo (-:
Grazie a tutti!

Answer 1

P

Classe di tutti i problemi che possono essere risolti da un deterministica macchina di Turing in tempo polinomiale.

NP

Classe di tutti i problemi che possono essere risolti da un non-deterministico macchina di Turing in tempo polinomiale (possono anche essere verificati da un deterministica macchina di Turing in tempo polinomiale. )

NP-Hard

Una classe di problemi che sono "almeno altrettanto duro come i problemi più duri in NP". Formalmente, un problema è in NP-Hard se e solo se v'è un problema NP-completo che è tempo polinomiale Turing riducibile ad esso; (Anche: sse può essere risolto in tempo polinomiale da una macchina di oracolo con un oracolo per il problema). E 'abbastanza ovvio dove il nome deriva da.

NPC

La classe di problemi che sono sia NP e NP-Hard. Per quanto riguarda la denominazione, anche wikipedia non è sicuro perché è chiamato così com'è.

Answer 2

La partenza di Let con "deterministico". Una macchina deterministica può essere in uno stato alla volta. Siamo in grado di fare in realtà li. Una macchina non deterministica è un costrutto teorico che può essere in più di uno stato alla volta. (C'è somiglianze con Quantum Computing qui, ma per i nostri scopi qui stanno fuorviante. Ignorarle.)

Se vogliamo risolvere un problema con una macchina deterministica, iniziamo in su, e passa attraverso una serie di passi per cercare di trovare un problema. Se modelliamo utilizza una macchina non deterministica, può passare attraverso tutti i possibili serie di operazioni allo stesso tempo.

L'insieme dei problemi che stiamo andando a preoccuparsi di problemi di decisione è: data una dichiarazione problema, c'è una soluzione o meno. Trovare una soluzione o per segnalare che non c'è nessuno. Ad esempio, si supponga di avere un insieme di istruzioni logiche: A o non-B, B o C o D, non-D o A o B, .... Dato un insieme arbitrario, è possibile trovare i valori di verità per tutte le variabili in modo tale che tutte le affermazioni sono vere?

Ora, consideriamo il P. Supponiamo che noi rappresentiamo la dimensione di un problema da n. La dimensione potrebbe essere il numero delle città in un problema del commesso viaggiatore, il numero di dichiarazioni logiche del problema di cui sopra, a prescindere. Dato un certo n, il problema richiede una certa quantità di risorse per risolvere in un dato sistema. Ora, se raddoppiamo le risorse o capacità di calcolo, che cosa accade alle dimensioni del problema che possiamo risolvere? Se il problema è di complessità polinomiale, il che significa in P, la dimensione sale di una certa frazione. Si potrebbe raddoppiare, o salire del 40%, o 10%. Al contrario, se è di complessità esponenziale, la dimensione va da un certo numero. Generalmente pensiamo di problemi P come problemi risolvibili ed esponenziale come irrisolvibile, come i problemi diventano grandi, anche se questa è una semplificazione. Da un punto di vista informale, complessità polinomiale è essere in grado di capire cose circa il problema sequenzialmente, mentre esponenziale è dover esaminare tutte le combinazioni possibili.

Si supponga che siamo in grado di risolvere il problema in tempo polinomiale su una macchina deterministica. Il problema è in P. Supponiamo possiamo risolvere in tempo polinomiale su una macchina non deterministica, che è la stessa cosa che essere in grado di verificare un progetto di soluzione in tempo polinomiale su una macchina deterministica. Allora il problema è in NP. Il trucco è che non siamo in grado di fare vere macchine non deterministiche, in modo che il fatto che un problema è in NP non significa che sia pratico da risolvere.

Ora al NP-completo. Tutti i problemi in P sono in NP. Per problemi A e B in NP, potremmo essere in grado di dire che se A è in P, quindi è B. Questo viene fatto trovando un modo per ribadire B come una sorta di problema. Un problema NP-completo è uno di questi che, se è in P, ogni problema in NP è in P. Come si può intuire, trovare un modo per ribadire ogni possibile problema, come uno in particolare non è stato facile, e io basta dire che il problema con istruzioni logiche sopra (il problema Satisfiability) è stato il primo dimostrato NP-completo. Dopo che era più facile, poiché era necessario soltanto dimostrare che se problema C era in P, quindi era Satisfiability.

Si ritiene generalmente che ci sono problemi che sono in NP, ma non P, e una prova è stato recentemente pubblicato (che può o non può rivelarsi valido). In tal caso, i programmi NP-completi sono i tipi più difficili di problemi in NP.

Ci sono problemi che non rientrano in questo stampo. Il problema del commesso viaggiatore, come normalmente poste, è quello di trovare il percorso più economico che collega tutte le città. Questo non è un problema di decisione, e non possiamo verificare direttamente qualsiasi soluzione proposta. Possiamo Ribadiamo come un problema decisionale: dato un costo C, c'è un percorso che è più conveniente che C? Questo problema è NP-completo, e con un po 'di lavoro si può risolvere il TSP originale su facilmente come quello modificato, NP-completo, la forma. Pertanto, il TSP è NP-difficile, dal momento che'S almeno altrettanto duro come un problema NP-completo.

Answer 3

NP è chiamata NP (non deterministico tempo polinomiale) per un problema NP può essere risolto in tempo polinomiale da una macchina di Turing non deterministica.

Answer 4

Cominciamo con NP: in NP, N è per "deterministico" e P è per "un tempo polinomiale". E 'la classe di problemi che possono essere risolti in tempo polinomiale se si dispone di una macchina di Turing non deterministica che può espandersi ad ogni ciclo di esplorare le possibilità in parallelo (la "Verifica la soluzione" definizione alternativa è diventato popolare di recente, ma non mettere in chiaro cosa significa "N"). La macchina non deterministica può essere paragonato ad un computer parallelo con un numero infinito di processori, e la capacità di fork() ad ogni istruzione.

Dicendo che un problema Q è significa "NP-hard" che qualsiasi problema in NP può essere ridotto al problema di Q (in tempo polinomiale). Dal momento che la relazione "può essere ridotto a" fra i problemi è una relazione d'ordine, si può pensare di "NP-hard" nel senso "almeno così difficile come tutti i problemi NP".

Un problema di "NP-completo" è semplicemente uno dei problemi in NP che è NP-hard. Immagino che classe di problemi aveva bisogno di un nome, ma non sono sicuro di come spiegare la scelta del termine "completo".

Answer 5

  

Ma cosa significa il determinismo ha a che fare con questo?

Wikipedia :

NP è l'insieme di tutti i problemi di decisione per i quali il 'yes'-risposte hanno prove in modo efficiente verificabili del fatto che la risposta è davvero 'sì'. Più precisamente, tali prove devono essere verificabili in tempo polinomiale da un deterministica macchina di Turing

Non sono sicuro circa la storia dei nomi però. EDIT: Ho congetture però. Quello che segue è la speculazione, ma non credo che sia irragionevole.

NP-Hard è un qualsiasi problema che è almeno altrettanto duro come i problemi più duri in NP. Pertanto, si potrebbe dire che il problema in questione avrebbe durezza NP., Quindi NP-Hard.

Se ogni singolo problema in NP-completo può essere risolto in fretta, poi ogni problema in NP può anche essere risolto in fretta. Pertanto, il set completo di problemi NP potrebbe essere risolto.

EDIT2 : di Wikipedia Complete (Complessità) articolo indica:

  

un problema computazionale è completa per una classe di complessità se lo è, in senso formale, uno dei "duri" o "più espressivi" problemi nella classe di complessità