Che cos'è un NP completo in informatica?

StackOverflow https://stackoverflow.com/questions/210829

Domanda

Che cos'è un problema NP-completo? Perché è un argomento così importante nell'informatica?

È stato utile?

Soluzione

NP sta per non deterministico polinomiale .

Ciò significa che il problema può essere risolto in tempo polinomiale usando una macchina di Turing non deterministica (come una normale macchina di Turing ma includendo anche una funzione di "scelta" non deterministica). Fondamentalmente, una soluzione deve essere testabile in poly time. In questo caso, e un problema NP noto può essere risolto utilizzando il problema dato con input modificato (un problema NP può essere ridotto al problema dato), allora il problema è NP completo.

La cosa principale da eliminare da un problema NP completo è che non può essere risolto in tempo polinomiale in alcun modo noto. NP-Hard / NP-Complete è un modo per dimostrare che determinate classi di problemi non sono risolvibili in tempo realistico.

Modifica: come altri hanno notato, ci sono spesso soluzioni di approssimazione per problemi NP-Complete. In questo caso, la soluzione di approssimazione solitamente fornisce un limite di approssimazione usando una notazione speciale che ci dice quanto è vicina l'approssimazione.

Altri suggerimenti

Che cos'è NP ?

NP è l'insieme di tutti i problemi di decisione (domande con una risposta sì-o-no ) per cui le risposte "sì" possono essere verificate in tempo polinomiale (O (n k ) dove n è la dimensione del problema e k è una costante) di una deterministica Turing machine . Il tempo polinomiale è talvolta usato come definizione di veloce o veloce .

Che cos'è P ?

P è l'insieme di tutti i problemi di decisione che possono essere risolti in tempo polinomiale da una macchina di Turing deterministica . Poiché possono essere risolti in tempo polinomiale, possono anche essere verificati in tempo polinomiale. Pertanto P è un sottoinsieme di NP.

Che cos'è NP-Complete ?

Un problema x che si trova in NP è anche in NP-Complete se e solo se ogni altro problema in NP può essere rapidamente trasformato (cioè nel tempo polinomiale) in x.

In altre parole:

  1. x è in NP e
  2. Ogni problema in NP è riducibile in x

Quindi, ciò che rende NP-Complete così interessante è che se uno qualsiasi dei problemi NP-Complete dovesse essere risolto rapidamente, allora tutti i problemi NP possono essere risolti velocemente.

Vedi anche il post Che cos'è " P = NP? & Quot ;, e perché è una domanda così famosa?

Che cos'è NP-Hard ?

NP-Hard sono problemi che sono tanto difficili quanto i problemi più difficili in NP. Si noti che anche i problemi NP-Complete sono NP-difficili. Tuttavia, non tutti i problemi NP-difficili sono NP (o addirittura un problema decisionale), nonostante il prefisso sia NP . Questo è NP in NP-hard non significa tempo polinomiale non deterministico . Sì, questo è confuso, ma il suo utilizzo è radicato e probabilmente non cambierà.

NP-Complete significa qualcosa di molto specifico e devi stare attento o sbaglierai la definizione. Innanzitutto, un problema NP è un problema sì / no tale che

  1. Esiste una prova del tempo polinomiale per ogni istanza del problema con un "sì" rispondi che la risposta è "sì" o (equivalentemente)
  2. Esiste un algoritmo del tempo polinomiale (possibilmente usando variabili casuali) che ha una probabilità diversa da zero di rispondere "sì" se la risposta a un'istanza del problema è "sì" e dirà " no " Il 100% delle volte se la risposta è "no". In altre parole, l'algoritmo deve avere un tasso di falsi negativi inferiore al 100% e nessun falso positivo.

Un problema X è NP-Complete se

  1. X è in NP e
  2. Per qualsiasi problema Y in NP, c'è una "riduzione" da Y a X: un algoritmo del tempo polinomiale che trasforma qualsiasi istanza di Y in un'istanza di X in modo tale che la risposta all'istanza Y sia "sì"; se e solo se la risposta X-instance è " yes " ;.

Se X è NP-completo ed esiste un algoritmo deterministico nel tempo polinomiale in grado di risolvere correttamente tutte le istanze di X (0% di falsi positivi, 0% di falsi negativi), allora qualsiasi problema in NP può essere risolto in deterministico -polynomial-time (dalla riduzione a X).

Finora, nessuno ha escogitato un algoritmo così deterministico nel tempo polinomiale, ma nessuno ha dimostrato che uno non esiste (c'è un milione di dollari per chiunque possa fare uno dei due: il P = problema NP ). Ciò non significa che non è possibile risolvere una particolare istanza di un problema NP-Complete (o NP-Hard). Significa solo che non puoi avere qualcosa che funzioni in modo affidabile su tutte le istanze di un problema nello stesso modo in cui puoi ordinare in modo affidabile un elenco di numeri interi. Potresti benissimo essere in grado di elaborare un algoritmo che funzionerà molto bene su tutte le istanze pratiche di un problema NP-Hard.

NP-Complete è una classe di problemi.

La classe P è costituita da quei problemi che sono risolvibili in tempo polinomiale . Ad esempio, potrebbero essere risolti in O (n k ) per una costante k, dove n è la dimensione dell'input. In poche parole, puoi scrivere un programma che verrà eseguito in ragionevole .

La classe NP è costituita da quei problemi che sono verificabili in tempo polinomiale. Cioè, se ci viene data una potenziale soluzione, allora potremmo verificare se la soluzione data è corretta in tempo polinomiale.

Alcuni esempi sono il problema della soddisfazione booleana (o SAT ) o il problema del ciclo hamiltoniano. Esistono molti problemi noti nella classe NP.

NP-Complet indica che il problema è almeno difficile come qualsiasi altro problema in NP.

È importante per l'informatica perché è stato dimostrato che qualsiasi problema in NP può essere trasformato in un altro problema in NP-complete. Ciò significa che una soluzione a qualsiasi problema NP completo è una soluzione a tutti i problemi NP.

Molti algoritmi di sicurezza dipendono dal fatto che non esistono soluzioni note per i problemi di NP. Avrebbe sicuramente un impatto significativo sull'informatica se venisse trovata una soluzione.

Fondamentalmente i problemi di questo mondo possono essere classificati come

& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 1) Problema irrisolvibile & Nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 2) Problema intrattabile & Nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 3) Problema NP & Nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 4) P-Problem

& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 1) Il primo non è una soluzione al problema. & Nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 2) Il secondo è il tempo esponenziale necessario (ovvero O (2 ^ n) sopra). & Nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 3) Il terzo si chiama NP. & Nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 4) Il quarto è un problema facile.

P: si riferisce a una soluzione del problema del tempo polinomiale.

NP: indica il tempo polinomiale ancora per trovare una soluzione. Non siamo sicuri che non esiste una soluzione Polynomial Time, ma una volta fornita una soluzione, questa soluzione può essere verificata in Polynomial Time.

NP completo: fa riferimento a Tempo polinomiale che dobbiamo ancora trovare una soluzione, ma può essere verificato in Tempo polinomiale. Il problema NPC in NP è il problema più difficile, quindi se possiamo dimostrare di avere una soluzione P al problema NPC, allora i problemi NP che si possono trovare nella soluzione P.

NP Hard: indica che il tempo polinomiale deve ancora trovare una soluzione, ma sicuramente non può essere verificato in tempo polinomiale. Il problema NP difficile supera la difficoltà NPC.

È una classe di problemi in cui dobbiamo simulare ogni possibilità per essere sicuri di avere la soluzione ottimale.

Esistono molte buone euristiche per alcuni problemi NP-Complete, ma sono solo un'ipotesi colta al massimo.

Se stai cercando un esempio di un problema NP completo, ti suggerisco di dare un'occhiata a 3-SAT .

La premessa di base è che hai un'espressione in forma normale congiuntiva , che è un modo di dicendo che hai una serie di espressioni unite da OR che tutto deve essere vero: 

(a or b) and (b or !c) and (d or !e or f) ...

Il problema 3-SAT è trovare una soluzione che soddisfi l'espressione in cui ciascuna delle espressioni OR ha esattamente 3 booleani da abbinare: 

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

Una soluzione a questa potrebbe essere (a = T, b = T, c = F, d = F). Tuttavia, non è stato scoperto alcun algoritmo che risolva questo problema nel caso generale in tempi polinomiali. Ciò significa che il modo migliore per risolvere questo problema è essenzialmente di indovinare e controllare una forza bruta e provare combinazioni diverse fino a quando non ne trovi una che funzioni.

La particolarità del problema 3-SAT è che QUALSIASI problema completo NP può essere ridotto a un problema 3-SAT. Ciò significa che se riesci a trovare un algoritmo a tempo polinomiale per risolvere questo problema, otterrai $ 1,000,000 , per non parlare del rispetto e dell'ammirazione degli informatici e dei matematici di tutto il mondo.

Onestamente, Wikipedia potrebbe essere il posto migliore per cercare una risposta a questo.

Se NP = P, allora possiamo risolvere problemi molto difficili molto più velocemente di quanto pensassimo di poter fare prima. Se risolviamo un solo problema NP-Complete in tempo P (polinomiale), allora può essere applicato a tutti gli altri problemi nella categoria NP-Complete.

Dobbiamo separare algoritmi e problemi. Scriviamo algoritmi per risolvere i problemi e si adattano in un certo modo. Sebbene questa sia una semplificazione, etichettiamo un algoritmo con una 'P' se il ridimensionamento è abbastanza buono, e 'NP' se non lo è.

È utile sapere cose sui problemi che stiamo cercando di risolvere, piuttosto che sugli algoritmi che usiamo per risolverli. Quindi diremo che tutti i problemi che hanno un algoritmo di ridimensionamento sono "in P". E quelli che hanno un algoritmo di ridimensionamento sono "in NP".

Ciò significa che molti problemi semplici sono "in NP" anche perché possiamo scrivere algoritmi sbagliati per risolvere problemi facili. Sarebbe bello sapere quali problemi in NP sono davvero difficili, ma non vogliamo solo dire "sono quelli per cui non abbiamo trovato un buon algoritmo per". Dopotutto, potrei trovare un problema (chiamalo X) che penso abbia bisogno di un algoritmo super-sorprendente. Dico al mondo che il miglior algoritmo che ho potuto inventare per risolvere male le scale X, e quindi penso che X sia un problema davvero difficile. Ma domani, forse qualcuno più intelligente di me inventa un algoritmo che risolve X ed è in P. Quindi questa non è un'ottima definizione di problemi difficili.

Tuttavia, in NP ci sono molti problemi per i quali nessuno conosce un buon algoritmo. Quindi se potessi dimostrare che X è un certo tipo di problema: uno in cui un buon algoritmo per risolvere X potrebbe anche essere usato, in qualche modo, per dare un buon algoritmo per ogni altro problema in NP. Bene, ora le persone potrebbero essere un po 'più convinte che X sia un problema davvero complicato. E in questo caso chiamiamo X NP-Complete.

Le definizioni per i problemi completi di NP sopra riportate sono corrette, ma ho pensato che avrei potuto chiarire la loro importanza filosofica in quanto nessuno ha ancora affrontato questo problema.

Quasi tutti i problemi complessi che affronterai saranno NP Complete. C'è qualcosa di molto fondamentale in questa classe, e che sembra essere solo computazionalmente diverso dai problemi facilmente risolvibili. In un certo senso hanno il loro sapore, e non è così difficile riconoscerli. Ciò significa sostanzialmente che qualsiasi algoritmo moderatamente complesso è impossibile da risolvere esattamente: pianificazione, ottimizzazione, impacchettatura, copertura ecc.

Ma non tutto è perduto se un problema che incontrerai è NP Complete. Esiste un campo vasto e molto tecnico in cui le persone studiano algoritmi di approssimazione, che ti daranno garanzie di essere vicini alla soluzione di un problema completo NP. Alcune di queste sono garanzie incredibilmente forti - per esempio, per 3sat, puoi ottenere una garanzia 7/8 attraverso un algoritmo davvero ovvio. Ancora meglio, in realtà, ci sono alcune euristiche molto forti, che eccellono nel dare grandi risposte (ma nessuna garanzia!) Per questi problemi.

Nota che due problemi molto famosi - isomorfismo grafico e factoring - non sono noti per essere P o NP.

Ho sentito una spiegazione, ovvero: " NP-Completezza è probabilmente una delle idee più enigmatiche nello studio degli algoritmi. & Quot; NP " sta per "tempo polinomiale non deterministico", ed è il nome di quella che viene chiamata una classe di complessità a cui possono appartenere i problemi. La cosa importante della classe di complessità NP è che i problemi all'interno di quella classe possono essere verificati da un algoritmo temporale polinomiale. Ad esempio, considera il problema del conteggio delle cose. Supponiamo che ci siano un mucchio di mele su un tavolo. Il problema è "quante mele ci sono?" Viene fornita una possibile risposta, 8. È possibile verificare questa risposta in tempi polinomiali utilizzando l'algoritmo di, duh, contando le mele. Il conteggio delle mele avviene nel tempo O (n) (che è notazione Big-oh), perché ci vuole un passo per contare ogni mela. Per n mele, hai bisogno di n passaggi. Questo problema è nella classe di complessità NP.

Un problema è classificato come NP-completo se si può dimostrare che è NP-Hard e verificabile in tempo polinomiale. Senza approfondire troppo la discussione su NP-Hard, basti dire che ci sono alcuni problemi ai quali non sono state trovate soluzioni temporali polinomiali. Cioè, ci vuole qualcosa come n! (n fattoriale) passaggi per risolverli. Tuttavia, se ti viene data una soluzione a un problema NP-Complete, puoi verificarlo in tempo polinomiale.

Un classico esempio di problema NP-Complete è The Travelling Salesman Problem. "

L'autore: ApoxyButt Da: http://www.everything2.com/title/NP-complete

Problema NP: -

  1. I problemi NP sono tali problemi che possono essere risolti in tempi polinomiali non deterministici.
  2. L'algoritmo non deterministico opera in due fasi.
  3. Stadio di ipotesi non deterministico & amp; & amp; Fase di verifica non deterministica.

Tipo di problema Np

  1. NP completo
  2. NP Hard

Problema NP completo: -

1 Il problema decisionale A si chiama NP completo se ha le seguenti due proprietà: -

  1. Appartiene alla classe NP.
  2. Ogni altro problema in NP può essere trasformato in P in tempo polinomiale.

Alcuni Ex: -

  • Problema allo zaino
  • problema con la somma del sottoinsieme
  • Problema relativo al vertice

I problemi NP-complete sono una serie di problemi per ognuno dei quali altri problemi NP possono essere ridotti in tempi polinomiali e la cui soluzione può ancora essere verificato in tempo polinomiale. Cioè, qualsiasi problema NP può essere trasformato in uno qualsiasi dei problemi NP-completi. & # 8211; Informalmente, un problema NP completo è un problema NP che è almeno "difficile". come qualsiasi altro problema in NP.

un problema NP è quello in cui un algoritmo informatico che verifica una soluzione può essere creato in tempo polinomiale.

un problema NP-completo è NP, ma anche se è possibile risolverlo in tempo polinomiale (chiamato P), tutti i problemi NP sono P.

Quindi inizia a fare crack.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top