Fondamentalmente hai ragione su P e NP, ma non su NP-hard e NP-complete.

Per i principianti, ecco le definizioni super concise delle quattro classi di complessità in questione:

• P è la classe di problemi decisionali che possono essere risolti in tempo polinomiale da una macchina di Turing deterministica.

• NP è la classe di problemi decisionali che possono essere risolti in tempo polinomiale da una macchina di Turing non deterministica. Allo stesso modo, è la classe di problemi che possono essere verificati in tempo polinomiale da una macchina di Turing deterministica.

• NP-hard è la classe di problemi decisionali a cui possono essere associati tutti i problemi in NP ridotto a tempo polinomiale da una macchina di Turing deterministica.

• NP-complete è lintersezione di NP-hard e NP. Allo stesso modo, NP-complete è la classe di problemi decisionali in NP a cui tutti gli altri problemi in NP possono essere ridotti in tempo polinomiale da una macchina di Turing deterministica.

E qui “sa Euler diagram da Wikipedia che mostra le relazioni tra queste quattro classi (supponendo che P non sia uguale a NP):

La parte con cui presumo tu “non abbia familiarità o che ti confonda di più è la nozione di una “riduzione del tempo polinomiale” dal problema X al problema Y. Una riduzione da X a Y è semplicemente un algoritmo A che risolve X facendo uso di qualche altro algoritmo B che risolve il problema Y. Questa riduzione è chiamata ” riduzione del tempo polinomiale “se tutte le parti di A diverse da B hanno una complessità temporale polinomiale. Come esempio banale, il problema di trovare lelemento più piccolo in un array è riducibile in tempo costante al problema dellordinamento, poiché puoi ordinare larray e quindi restituire il primo elemento dellarray ordinato.

Uno cosa che è facile perdere della definizione NP-difficile è che la riduzione va dai problemi NP al problema NP-difficile, ma non necessariamente viceversa . Ciò significa che i problemi NP-hard potrebbero essere in NP, o in una classe di complessità molto più alta (come puoi vedere dal diagramma di Eulero), oppure potrebbero non essere nemmeno problemi decidibili.Ecco perché le persone spesso dicono qualcosa come “NP-difficile significa almeno difficile quanto NP” quando cercano di spiegare queste cose in modo informale.

Il problema dellarresto è un buon esempio di un problema NP-difficile “chiaramente non è in NP, come Wikipedia spiega :

È facile dimostrare che il problema dellarresto è NP-difficile ma non NP-completo. Ad esempio, il problema della soddisfacibilità booleano può essere ridotto al problema dellarresto trasformandolo nella descrizione di una macchina di Turing che prova tutte le assegnazioni di valori di verità e quando ne trova uno che soddisfa la formula si ferma e altrimenti entra in un ciclo infinito. È anche facile vedere che il problema dellarresto non è in NP poiché tutti i problemi in NP sono decidibili in un numero finito di operazioni, mentre il problema dellarresto, in generale, è indecidibile.

Commenti

• @Nakano Intuitively, it ‘ sa ” riduzione ” nel senso che un problema viene trasformato in un sottoproblema di un altro problema. Il fatto che alcune di queste riduzioni aumentino la complessità invece di diminuirla a causa di una cattiva scelta di ” sottoproblema ” significa semplicemente che non useresti mai queste riduzioni in qualsiasi codice del mondo reale. Anche se ad essere onesti NP-hard mi sembra una classe strana e non particolarmente interessante; potrebbe essere più utile ignorarlo e pensare a NP-complete come linsieme di problemi NP a cui riducono tutti gli altri problemi NP.
• @Nakano stackoverflow.com/questions/12637582/… Credo che la risposta breve sia che quando si parla di fattorizzazione dei numeri interi come NP, ‘ normalmente si parla di numeri interi davvero enormi, per i quali generalmente inizi a fare le tue dimostrazioni di O grande con n come ” il numero di bit che lintero occupa in memoria ” invece di ” il numero di numeri interi passati alla funzione “.
• @Nakano: nella notazione O grande, n è una misura per la dimensione dellinput (numero di elementi, byte, cifre, ecc.), Non il valore del input.
• @Nakano La risposta breve è che ‘ stai bene, ed è per questo che quando fai time co mplexity analaysis devi sempre specificare cosa significa n . Laffermazione che n è ” la dimensione dellinput ” è semplicemente un breve riassunto di come normalmente scegliamo di definire n. ‘ non fa parte delle rigorose definizioni di notazione O grande o complessità temporale. Credo che tu abbia ragione quando dici che la fattorizzazione dei numeri interi è O (sqrt (n)) quando n è il valore dellinput. Accade così che i risultati di complessità dove n significa dimensione sono di solito molto più utili nella pratica di quelli in cui n significa valore.
• @Nakano It ‘ Vale anche la pena tenere a mente che tecnicamente devi anche definire la complessità temporale delle tue operazioni primitive (addizione, multiplicazione, lettura dalla memoria, scrittura nella memoria, confronto di due numeri). Il più delle volte assumiamo che tutte queste primitive siano costanti o contiamo solo un tipo di operazione (ad esempio, per gli algoritmi di ordinamento tradizionalmente contiamo i confronti). Sospetto che i risultati per la fattorizzazione di interi non ‘ presumano che tutte queste operazioni siano a tempo costante come facciamo di solito, altrimenti la dimensione del numero non ‘ è molto importante.

La fattorizzazione intera viene citata come esempio di NP, ma personalmente non capisco perché non sia P, poiché la fattorizzazione di prova richiede tempo O (sqrt (n)).

Ai fini delle classi di complessità, n è la lunghezza dellinput. Quindi, se desideri scomporre in fattori interi k, n non è k ma log k, il numero di bit (o qualsiasi altra cosa) necessari per annotare il numero. Quindi la fattorizzazione dei numeri interi è O(sqrt(k)) come dici tu, ma questo è O(sqrt(2n)) che è O(2(n/2)).

NP-Hard presumo sia pieno di incognite. Difficile da verificare, difficile da risolvere.

No. NP-Hard riguarda semplicemente quanto sia difficile risolvere un problema.

I problemi NP-Hard sono almeno difficili come il problema più difficile in NP. Sappiamo che sono almeno così difficili, perché se avessimo un algoritmo tempo polinomiale per un problema NP-Hard, potremmo adattare quellalgoritmo a qualsiasi problema in NP.

NP-Complete Non capisco affatto

NP- Completo significa che un problema è sia NP che NP-Hard. Significa che possiamo verificare una soluzione rapidamente (NP), ma è difficile almeno quanto il problema più difficile in NP (NP-Hard).

Non so veramente cosa significhi non essere deterministico.

Non -determinismo è una definizione alternativa di NP. Una macchina turing non deterministica è effettivamente in grado di duplicarsi in qualsiasi momento e fare in modo che ogni duplicato prenda un percorso di esecuzione diverso. Sotto questa definizione, NP è linsieme dei problemi che possono essere risolti in tempo polinomiale da un computer che può duplicarsi liberamente. Risulta che questo è esattamente lo stesso insieme di problemi che possono essere verificati in tempo polinomiale.

Commenti

• Quindi è possibile per $ O ( n ^ k) $ time algoritmi per essere problemi NP?
• k è un numero reale costante? Sì. Tutti i problemi P sono anche problemi NP. Ovviamente, tutto ciò che puoi risolvere in tempo polinomiale può essere verificato anche in tempo polinomiale.
• Come vengono effettivamente definite qui lunghezza / dimensione? Ad esempio, potrei semplicemente scrivere $ n $ in una base grande e diminuirne la lunghezza quando viene scritto. E i problemi che non ‘ trattano esplicitamente interi, ma diciamo grafici con vertici $ V $ e bordi $ E $, ecc.
• @Nakano, in realtà una base ampia non ‘ la cambierebbe, perché sarebbe solo una differenza di fattore costante. Quindi ‘ t non avrà effetto polinomiale rispetto a non polinomiale. Tuttavia, se scrivessi il numero in unario, lo cambierebbe.
• @Nakano, hmm … Non ‘ oserei provare a spiegare la complessità classi a un bambino di cinque anni. : P

La prima cosa da capire è che P e NP classifica lingue , non problemi . Per capire cosa significa, abbiamo bisogno prima di alcune altre definizioni.

Un alfabeto è un insieme finito non vuoto di simboli.

{0 , 1} è un alfabeto così come il set di caratteri ASCII. {} non è un alfabeto perché è vuoto. N (i numeri interi) non è un alfabeto perché non è finito.

Sia Σ essere un alfabeto. Una concatenazione ordinata di un numero finito di simboli da Σ è chiamata parola su Σ .

La stringa 101 è una parola sopra lalfabeto {0, 1}. La parola vuota (spesso scritta come ε ) è una parola su qualsiasi alfabeto. La stringa penguin è una parola sopra lalfabeto contenente i caratteri ASCII. La notazione decimale del numero π non è una parola sopra lalfabeto {., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} perché non è finito.

Il lunghezza di una parola w , scritta come | w |, è il numero di simboli in esso.

Ad esempio, | hello | = 5 e | ε | = 0. Per qualsiasi parola w , | w | ∈ N e quindi finito.

Sia Σ essere un alfabeto. Il set Σ ^＊ contiene tutte le parole su Σ , incluso ε . Il set Σ ⁺ contiene tutte le parole su Σ , escluso ε . Per n ∈ N , Σ ⁿ è linsieme di parole di lunghezza n .

Per ogni alfabeto Σ , Σ ^＊ e Σ ⁺ sono infinite set numerabili .Per il set di caratteri ASCII Σ _ASCII , le espressioni regolari .* e .+ denota Σ _ASCII ^＊ e Σ _ASCII ⁺ rispettivamente.

{0, 1} ⁷ è linsieme di codici ASCII a 7 bit {0000000, 0000001,…, 1111111}. {0, 1} ³² è linsieme di valori interi a 32 bit.

Sia Σ un alfabeto e L ⊆ Σ ^＊ . L è chiamato lingua su Σ .

Per un alfabeto Σ , il set vuoto e Σ ^＊ sono linguaggi banali su Σ . Il primo è spesso indicato come linguaggio vuoto . La lingua vuota {} e la lingua contenente solo la parola vuota { ε } sono diverse.

Il sottoinsieme di {0, 1} ³² che corrisponde a valori a virgola mobile IEEE 754 non NaN è un linguaggio finito.

Le lingue possono contenere un numero infinito di parole ma ogni lingua è numerabile. Linsieme di stringhe {1, 2,…} che denotano gli interi in notazione decimale è una lingua infinita sullalfabeto {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9}. La serie infinita di stringhe {2, 3, 5, 7, 11, 13,…} che indica i numeri primi in notazione decimale è un proprio sottoinsieme. Il linguaggio contenente tutte le parole che corrispondono allespressione regolare [+-]?\d+\.\d*([eE][+-]?\d+)? è un linguaggio sul set di caratteri ASCII (che denota un sottoinsieme delle espressioni a virgola mobile valide come definito dal linguaggio di programmazione C).

Non esiste una lingua contenente tutti i numeri reali (in nessuna notazione) perché linsieme di numeri reali non è numerabile.

Let Σ essere un alfabeto e L ⊆ Σ ^＊ . Una macchina D decide L se per ogni input w ∈ Σ ^＊ calcola la funzione caratteristica χ _L ( w ) in tempo finito. La funzione caratteristica è definita come

χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.

Questa macchina è chiamata decider per L . Scriviamo “ D ( w ) = x ” per “dato w , D restituisce x “.

Esistono molti modelli di macchina. Quello più generale che è oggi in uso pratico è il modello di una macchina di Turing . Una macchina di Turing ha una memoria lineare illimitata raggruppata in celle. Ogni cella può contenere esattamente un simbolo di un alfabeto in qualsiasi momento. La macchina di Turing esegue il suo calcolo come una sequenza di passaggi di calcolo. In ogni passaggio, può leggere una cella, eventualmente sovrascriverne il valore e spostare la testina di lettura / scrittura di una posizione sulla cella sinistra o destra. Lazione che la macchina eseguirà è controllata da un automa a stati finiti.

Una macchina ad accesso casuale con un insieme finito di istruzioni e memoria illimitata è un altro modello di macchina potente quanto il modello di macchina di Turing.

Per il bene di questa discussione, non ci preoccuperemo del preciso modello di macchina che utilizziamo ma è sufficiente dire che la macchina ha ununità di controllo deterministica finita, memoria illimitata ed esegue un calcolo come una sequenza di passaggi può essere contato.

Dato che lhai usato nella tua domanda, presumo che tu “abbia già familiarità con la notazione” big-O “ quindi ecco solo un rapido ripasso.

Sia f : N → essere una funzione.Linsieme O ( f ) contiene tutte le funzioni g : N → N per cui esistono costanti n ₀ ∈ N e c ∈ N tale che per ogni n ∈ N con n > n ₀ è vero che g ( n ) ≤ c f ( n ).

Ora siamo pronti ad affrontare la vera domanda.

La classe P contiene tutte le lingue L per le quali esiste una macchina di Turing D che decide L e una costante k ∈ N tale che per ogni input w , D si interrompe dopo al massimo T (| w |) passaggi per una funzione T ∈ O ( n ↦ n ^k ).

Da O ( n ↦ n ^k ), sebbene matematicamente corretto, è scomodo da scrivere e leggere, la maggior parte delle persone – ad essere onesti, tutti tranne me stesso – di solito scrive semplicemente O(n^k ).

Nota che il limite dipende dalla lunghezza w . Pertanto, largomento che fai per la lingua dei numeri primi è corretto solo per i numeri nelle codifiche unaray , dove per la codifica w di un numero n , la lunghezza della codifica | w | è proporzionale a n . Nessuno userebbe mai una codifica del genere nella pratica. Utilizzando un algoritmo più avanzato rispetto al semplice tentativo di tutti i fattori possibili, si può mostrare, tuttavia, che il linguaggio dei numeri primi rimane in P se gli input sono codificati in binario (o in qualsiasi altra base). (Nonostante lenorme interesse, questo potrebbe essere dimostrato solo da Manindra Agrawal, Neeraj Kayal e Nitin Saxena in un documento premiato nel 2004, quindi puoi indovinare che il lalgoritmo non è molto semplice.)

I linguaggi banali {} e Σ ^＊ e il linguaggio non banale { ε } sono ovviamente in P (per qualsiasi alfabeto Σ ). Puoi scrivere funzioni nel tuo linguaggio di programmazione preferito che prendono una stringa come input e restituiscono un booleano che dice se la stringa è una parola del linguaggio per ognuna di queste e prova che la tua funzione ha una complessità di runtime polinomiale?

Ogni lingua normale (una lingua descritta da unespressione regolare) è in P .

Sia Σ un alfabeto e L ⊆ Σ ^＊ . Una macchina V che accetta una tupla codificata di due parole w , c ∈ Σ ^＊ e restituisce 0 o 1 dopo un numero finito di passaggi è un verificatore per L se ha le seguenti proprietà.

• Dato ( w , c ), V restituisce 1 solo se w ∈ L .
• Per ogni w ∈ L , ci esiste un c ∈ Σ ^＊ tale che V ( w , c ) = 1.

La c nella definizione precedente è chiamata testimone (o certificato ) .

Un verificatore può fornire falsi negativi per il testimone sbagliato anche se w è effettivamente in L . Non è tuttavia consentito fornire falsi positivi. È inoltre richiesto che per ogni parola nella lingua esista almeno un testimone.

Per la lingua COMPOSITE, che contiene le codifiche decimali di tutti i numeri interi non primi , un testimone potrebbe essere una fattorizzazione. Ad esempio, (659, 709) è un testimone per 467231 ∈ COMPOSITE. Puoi facilmente verificarlo su un foglio di carta senza il testimone dato, provare che 467231 non è primo sarebbe difficile senza usare un computer.

Non abbiamo detto nulla su come può essere un testimone appropriato trovato. Questa è la parte non deterministica.

La classe NP contiene tutte le lingue L per le quali esiste una macchina di Turing V che verifica L e una costante k ∈ N tale che per ogni input ( w , c ), V si ferma dopo al massimo T (| w |) passaggi per una funzione T ∈ O ( n ↦ n^k ).

Tieni presente che la definizione precedente implica che per ogni w ∈ L esiste un testimone c con | c | ≤ T (| w |). (La macchina di Turing non può assolutamente guardare altri simboli del testimone.)

NP è un superset di P (perché?). Non è noto se esistano lingue che sono in NP ma non in P .

La fattorizzazione intera non è una lingua in sé. Tuttavia, possiamo costruire un linguaggio che rappresenti il problema decisionale ad esso associato. Ovvero, un linguaggio che contiene tutte le tuple ( n , m ) tali che n abbia un fattore d con d ≤ m . Chiamiamo questo linguaggio FATTORE. Se si dispone di un algoritmo per decidere FACTOR, può essere utilizzato per calcolare una fattorizzazione completa con solo un overhead polinomiale eseguendo una ricerca binaria ricorsiva per ogni fattore primo.

È facile mostrare che FACTOR è in NP . Un testimone appropriato sarebbe semplicemente il fattore d stesso e tutto ciò che il verificatore dovrebbe fare è verificare che d ≤ m e n mod d = 0. Tutto questo può essere fatto in tempo polinomiale. (Ricorda, ancora una volta, che è la lunghezza della codifica che conta e che è logaritmica in n .)

Se puoi dimostrare che FACTOR è anche in P , puoi essere certo di ottenere molti fantastici premi. (E hai rotto una parte significativa della crittografia odierna.)

Per ogni lingua in NP , esiste un algoritmo di forza bruta che decide in modo deterministico. Esegue semplicemente una ricerca esaustiva su tutti i testimoni. (Nota che la lunghezza massima di un testimone è delimitata da un polinomio.) Quindi, il tuo algoritmo per decidere PRIMES era in realtà un algoritmo di forza bruta per decidere COMPOSITO.

Per rispondere alla tua domanda finale, dobbiamo introdurre la riduzione . Le riduzioni sono un concetto molto potente dellinformatica teorica. Ridurre un problema a un altro significa fondamentalmente risolvere un problema risolvendone un altro problema.

Siano Σ un alfabeto e A e B essere lingue su Σ . A è tempo polinomiale molti-uno riducibile a B se esiste una funzione f : Σ ^＊ → Σ ^＊ con le seguenti proprietà.

• w ∈ A   ⇔   f ( w ) ∈ B   per tutti w ∈ Σ ^＊ .
• La funzione f può essere calcolata da una macchina di Turing per ogni input w in un numero di passaggi delimitato da un polinomio in | w |.

In questo caso, scriviamo A ≤ _p B .

Per ad esempio, sia A il linguaggio che contiene tutti i grafici (codificati come matrice di adiacenza) che contengono un triangolo. (Un triangolo è un ciclo di lunghezza 3.) Sia inoltre B il linguaggio che contiene tutte le matrici con traccia diversa da zero. (La traccia di una matrice è la somma dei suoi principali elementi diagonali.) Allora A è polinomio tempo molti-uno riducibile a B . Per dimostrarlo, dobbiamo trovare una funzione di trasformazione appropriata f . In questo caso, possiamo impostare f per calcolare la 3 ^rd potenza della matrice di adiacenza. Ciò richiede due prodotti matrice-matrice, ciascuno dei quali ha una complessità polinomiale.

È banalmente vero che L ≤ _p L . (Puoi dimostrarlo formalmente?)

Lo applicheremo a NP ora.

Una lingua L è NP -hard se e solo se L “≤ _p L per ogni lingua L ” ∈ NP .

Un NP linguaggio difficile può o non può essere in NP stesso.

Una lingua L è NP -completa se e solo se

• L ∈ NP e
• L è NP -hard.

Il linguaggio NP più famoso è SAT. Contiene tutte le formule booleane che possono essere soddisfatte. Ad esempio, ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Un testimone valido è { a = 1, b = 0}. La formula ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Come lo dimostreresti?)

Non è difficile dimostrare che SAT ∈ NP . Per mostrare la durezza NP di SAT è un po di lavoro, ma è stato fatto nel 1971 da Stephen Cook .

Una volta che un linguaggio completo NP era noto, era relativamente semplice mostrare la completezza NP di altri linguaggi tramite la riduzione. Se la lingua A è nota per essere NP -hard, significa che A ≤ _p B mostra che anche B è NP duro (tramite la transitività di “≤ _p “). Nel 1972 Richard Karp ha pubblicato un elenco di 21 lingue che poteva mostrare come NP complete tramite la riduzione (transitiva) di SAT. (Questo è lunico documento in questa risposta che in realtà ti consiglio di leggere. A differenza degli altri, non è difficile da capire e dà unottima idea di come funziona la dimostrazione della completezza di NP tramite la riduzione. )

Infine, un breve riassunto. Utilizzeremo i simboli NPH e NPC per indicare le classi dei linguaggi NP -hard e NP -completi rispettivamente.

• P ⊆ NP
• NPC ⊂ NP e NPC ⊂ NPH , in realtà NPC = NP ∩ NPH per definizione
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

Si noti che linclusione NPC ⊂ NP è corretta anche nel caso in cui P = NP . Per vedere questo, renditi chiaro che nessun linguaggio non banale può essere ridotto a un linguaggio banale e ci sono anche linguaggi banali in P come lingue non banali in NP . Thi s è un caso dangolo (non molto interessante), però.

Addendum

La tua principale fonte di confusione sembra essere che stavi pensando alla “ n “in” O ( n ↦ f ( n )) “Come l interpretazione dellinput di un algoritmo quando si riferisce effettivamente alla lunghezza dellinput. Questa è una distinzione importante perché significa che la complessità asintotica di un algoritmo dipende dalla codifica utilizzata per linput.

Questa settimana, un nuovo record per il più grande Mersenne prime è stato raggiunto. Il numero primo più grande attualmente noto è 2 ^{74   207   281} – 1. Questo numero è enorme che mi fa venire il mal di testa, quindi ne userò uno più piccolo nel seguente esempio: 2 ³¹ – 1 = 2   147   483   647. Può essere codificato in diversi modi.

• dal suo esponente di Mersenne come numero decimale: 31 (2 byte)
• come numero decimale: 2147483647 (10 byte)
• come unario numero: 11111…11 dove … deve essere sostituito da 2   147   483   altri 640 1 s (quasi 2 GiB)

Tutte queste stringhe codificano lo stesso numero e dato uno qualsiasi di questi, possiamo facilmente costruire qualsiasi altra codifica dello stesso numero. (Puoi sostituire la codifica decimale con binario, ottale o esadeci mal se vuoi. Cambia la lunghezza solo di un fattore costante.

Lalgoritmo ingenuo per testare la primalità è solo polinomiale per codifiche unarie. Il AKS primality test è polinomiale per decimale (o qualsiasi altra base b ≥ 2 ).Il test di primalità di Lucas-Lehmer è lalgoritmo più noto per i numeri primi di Mersenne M _p con p un primo dispari ma è ancora esponenziale nella lunghezza della codifica binaria dellesponente di Mersenne p (polinomio in p ).

Se vogliamo parlare della complessità di un algoritmo, è molto importante che sia molto chiaro quale rappresentazione usiamo. In generale, si può presumere che venga utilizzata la codifica più efficiente. Cioè, binario per interi. (Nota che non tutti i numeri primi sono numeri primi di Mersenne, quindi luso dellesponente di Mersenne non è uno schema di codifica generale.)

Nella crittografia teorica, molti algoritmi ricevono formalmente una stringa completamente inutile di k 1 s come primo parametro. Lalgoritmo non guarda mai questo parametro ma gli consente di essere formalmente polinomiale in k , che è il parametro di sicurezza utilizzato per ottimizzare la sicurezza della procedura.

Per alcuni problemi per i quali il linguaggio decisionale nella codifica binaria è NP -completo, il linguaggio decisionale non è più NP -completa se la codifica dei numeri incorporati è impostata su unaria. I linguaggi decisionali per altri problemi rimangono NP completi anche allora. Questi ultimi sono chiamati fortemente NP -complete . Lesempio più noto è bin packing .

È anche (e forse più) interessante vedere come la complessità di un algoritmo cambia se linput è compresso . Per lesempio dei numeri primi di Mersenne, abbiamo visto tre codifiche, ciascuna delle quali è logaritmicamente più compressa rispetto al suo predecessore.

Nel 1983, Hana Galperin e Avi Wigderson ha scritto un documento interessante sulla complessità degli algoritmi di grafi comuni quando la codifica di input del grafico è compressa logaritmicamente. Per questi input, il linguaggio dei grafici contenenti un triangolo dallalto (dove era chiaramente in P ) diventa improvvisamente NP -completo.

E quello “s perché classi di lingue come P e NP sono definite per lingue , non per problemi .

Commenti

• Questa risposta probabilmente non è utile per il livello di comprensione del richiedente. Leggi le altre risposte e guarda con cosa sta lottando Nanako. Pensi questo la risposta lo aiuterà?
• Questa risposta potrebbe non aiutare OP, ma sicuramente aiuta altri lettori (me compreso).
• risposta molto utile! Dovrei considerare di correggere i simboli matematici in modo non corretto visualizzato.

Cercherò di darti una definizione meno informale per lo stesso.

Problemi P: problemi che possono essere risolti in tempo polinomiale. Contiene problemi che possono essere risolvibili in modo efficiente.

Problema NP: problemi che possono essere verificati in polyno tempo mial. Ad esempio: venditore itinerante, progettazione di circuiti. I problemi NP sono una specie di puzzle (come il sudoku). Data una soluzione corretta per il problema, possiamo verificare la nostra soluzione molto velocemente, ma se effettivamente proviamo a risolverlo potrebbe volerci uneternità.

Ora, P vs NP chiede effettivamente se un problema la cui soluzione può essere rapidamente verificato per essere corretto, esiste sempre un modo rapido per risolverlo. Quindi scrivendo in termini matematici: NP è un sottoinsieme di P o no?

Ora tornando a NP completo: questi sono i problemi veramente difficili dei problemi NP. Quindi, se cè un modo più veloce per risolvere NP complete, allora NP complete diventa P e i problemi NP collassano in P.

NP difficile: i problemi che non possono essere controllati nel tempo polinomiale sono np difficili. Ad esempio, scegliere la mossa migliore negli scacchi è uno di questi.

Se qualcosa non è chiaro, prova a guardare questo video: https://www.youtube.com/watch?v=YX40hbAHx3s

Spero che questo fornisca un contorno sfocato.