P=NP
ciao a tutti,sono nuovo in questo forum e volevo chiedervi una cosa.
se si riuscisse a dimostrare che:
SAT (Boolean satisfiability problem) appartiene alla classe P,
allora risulterebbe vera la relazione P=NP ?
grazie in anticipo.
se si riuscisse a dimostrare che:
SAT (Boolean satisfiability problem) appartiene alla classe P,
allora risulterebbe vera la relazione P=NP ?
grazie in anticipo.
Risposte
da profano direi di no, per definizione di P e di NP.
p.s.:hai dimostrato che sat appartiene a P ?
p.s.:hai dimostrato che sat appartiene a P ?
no,MAGARI!!!!
era solo una curiosita...
ma allora come si fa a dimostrare che P=NP?
era solo una curiosita...
ma allora come si fa a dimostrare che P=NP?
guarda che ho scritto che sono profano... quindi attendo anche io delucidazioni in merito.
ciao
ciao
ma allora dato che SAT è un problema NP completo se si riesce a di mostrare che appartiene a P
risulterebbe vera la relazione P=NP ?
aiuto!
risulterebbe vera la relazione P=NP ?
aiuto!
Io direi di si, poichè un problema NP-completo è un problema, diciamo, "più difficile" di ogni altro problema della classe NP. Quindi se si trovasse un algoritmo di complessità polinomiale rispetto alla dimensione dell'input per risolvere un problema NP-completo, proprio per la definizione di NP-completezza potemmo risolvere ancora in tempo polinomiale ogni altro problema di NP, e di conseguenza non si avrebbe più distinzione fra P=NP.
Anzi, credo che la classe degli NP-completi sia stata introdotta apposta per avere un'idea di come procedere per dimostrare P=NP: trovare un algoritmo per un solo problema, se esiste, è fattibile, trovarne uno per ognuno dei "tanti" problemi della classe NP, è impossibile.
Ho detto scemenze?
Anzi, credo che la classe degli NP-completi sia stata introdotta apposta per avere un'idea di come procedere per dimostrare P=NP: trovare un algoritmo per un solo problema, se esiste, è fattibile, trovarne uno per ognuno dei "tanti" problemi della classe NP, è impossibile.
Ho detto scemenze?
dopo un rapido salto su wiki devo ritrattare cio' che ho detto nel mio primo post ed ammettere la mia incompetenza su tali questioni, almeno per ora.
ciao
alessandro
ciao
alessandro
ok grazie mille
Salve,
forse rispondo troppo tardi.... penso che possa risultare utile cominque.
Dunque la risposta alla domanda:
"se si riuscisse a dimostrare che:
SAT (Boolean satisfiability problem) appartiene alla classe P,
allora risulterebbe vera la relazione P=NP ? "
è SI!
Con questo non vuol dire che siamo a conoscenza di un algoritmo che risolve SAT in tempo polinomiale (cioè che SAT sia in P),
ma l'implicazione della domanda è vera!
Infatti se riuscissimo a dimostrare che SAT è in P siccome sappiamo che SAT è NP-completo(e quindi in NP) allora avremmo che le due classi (P ed NP) devono per forza coincidere.
Cmq si ritiene che P sia diverso da NP quindi è fortemente improbabile che si riesca a trovare un algoritmo che mi risolva SAT in tempo polinomiale.
Spero di essere stato chiaro....per ulteriori chiarimenti consiglio un libro veramente esplicativo:"Automi,linguaggi e calcolabilità" di Hopcroft-Motwani-Ullman.
(curiosità: se dovessi dimostrare che SAT è in P e quindi che p=NP vinceresti un milione di dollari!!!....c'è infatti un'associazione che offre tale somma a chi riesce a DIMOSTRARE che P=NP oppure che P è diverso da NP; inoltre le implicazione se P=NP sarebbero non poche e non di poco conto; infatti potremmo riuscire a trovare algoritmi (quindi soluzioni NON approssimate in tempo polinomiale) per problemi tipo: CSAT,k-SAT, NODE COVER, COMMESSO VIAGGIATORE, INSIEME INDIPENDENTE, CIRCUITO HAMILTONIANO....solo per citarni alcuni di problemi NP-completi)
ciao
________________________________________________________________________________________________
Legge di Hofstadter:"ci vuole sempre più tempo di quanto si pensi,anche tenendo conto della Legge di Hofstadter".
forse rispondo troppo tardi.... penso che possa risultare utile cominque.
Dunque la risposta alla domanda:
"se si riuscisse a dimostrare che:
SAT (Boolean satisfiability problem) appartiene alla classe P,
allora risulterebbe vera la relazione P=NP ? "
è SI!
Con questo non vuol dire che siamo a conoscenza di un algoritmo che risolve SAT in tempo polinomiale (cioè che SAT sia in P),
ma l'implicazione della domanda è vera!
Infatti se riuscissimo a dimostrare che SAT è in P siccome sappiamo che SAT è NP-completo(e quindi in NP) allora avremmo che le due classi (P ed NP) devono per forza coincidere.
Cmq si ritiene che P sia diverso da NP quindi è fortemente improbabile che si riesca a trovare un algoritmo che mi risolva SAT in tempo polinomiale.
Spero di essere stato chiaro....per ulteriori chiarimenti consiglio un libro veramente esplicativo:"Automi,linguaggi e calcolabilità" di Hopcroft-Motwani-Ullman.
(curiosità: se dovessi dimostrare che SAT è in P e quindi che p=NP vinceresti un milione di dollari!!!....c'è infatti un'associazione che offre tale somma a chi riesce a DIMOSTRARE che P=NP oppure che P è diverso da NP; inoltre le implicazione se P=NP sarebbero non poche e non di poco conto; infatti potremmo riuscire a trovare algoritmi (quindi soluzioni NON approssimate in tempo polinomiale) per problemi tipo: CSAT,k-SAT, NODE COVER, COMMESSO VIAGGIATORE, INSIEME INDIPENDENTE, CIRCUITO HAMILTONIANO....solo per citarni alcuni di problemi NP-completi)
ciao
________________________________________________________________________________________________
Legge di Hofstadter:"ci vuole sempre più tempo di quanto si pensi,anche tenendo conto della Legge di Hofstadter".
....per completezza di informazione voglio precisare che quanto detto è espresso con un teorema:
"SE UN PROBLEMA NP-COMPLETO X è IN P, ALLORA P=NP."
Questo teorema ovviamente ha la sua dimostrazione...ma ora si entrerebbe troppo nel tecnico...cmq se dovesse servire a qualcuno la posso postare...
ciao..
________________________________________________________________________________________________
Legge di Hofstadter:"ci vuole sempre più tempo di quanto si pensi,anche tenendo conto della Legge di Hofstadter".
"SE UN PROBLEMA NP-COMPLETO X è IN P, ALLORA P=NP."
Questo teorema ovviamente ha la sua dimostrazione...ma ora si entrerebbe troppo nel tecnico...cmq se dovesse servire a qualcuno la posso postare...
ciao..
________________________________________________________________________________________________
Legge di Hofstadter:"ci vuole sempre più tempo di quanto si pensi,anche tenendo conto della Legge di Hofstadter".
"EternaGhirlandaBrillante":
inoltre le implicazione se P=NP sarebbero non poche e non di poco conto; infatti potremmo riuscire a trovare algoritmi (quindi soluzioni NON approssimate in tempo polinomiale) per problemi tipo: CSAT,k-SAT, NODE COVER, COMMESSO VIAGGIATORE, INSIEME INDIPENDENTE, CIRCUITO HAMILTONIANO....solo per citarni alcuni di problemi NP-completi)
La cosa comica sarebbe se qualcuno riuscisse a trovare un algoritmo polinomiale, ma con ordine pari a $10^23$ o simile per SAT... troveremmo P=NP, ma i problemi tipo SAT rimarrebbe comunque più conveniente, per istanze di interesse pratico, usare un algoritmo esponenziale (che già comunque è di per se inapplicabile) piuttosto che quello polinomiale...
"EternaGhirlandaBrillante":
Cmq si ritiene che P sia diverso da NP quindi è fortemente improbabile che si riesca a trovare un algoritmo che mi risolva SAT in tempo polinomiale.
Beh, diciamo che molta nomenklatura accademica lo ritiene, e più o meno sono gli stessi che scrivono su manuali e libri di testo che "si rtitiene"...
In realtà, ragionando in prospettiva, le conseguenze della coincidenza tra P e NP sono molto più stimolanti. L'idea di fondo è che siamo noi umani un po' cialtroni e ottusi che non sappiamo trovare algoritmi polinomiali _E_ rapidamente computabili per quei problemi, non è la Natura che si è divertita a renderli computazionalmente ardui e quasi insolubili. Non sopravvalutiamoci nella nostra sbornia collettiva di formalismo bourbakista e di iperfetazione disciplinare: ne sappiamo sempre troppo poco. Le idee alla base sono sempre quelle, e sono sempre merce rara, più o meno ben vestite che siano.
Tra l'altro una "dimostrazione" implicita sarebbe semplicemente l'ideazione di un algoritmo in tempo polinomiale per un problema NP (per un noto teorema di trasformazione, se una soluzione in P esiste per uno dei problemi NP-completi, allora esiste soluzione in P per tutti quelli della medesima classe), e quindi può azzeccarla perfino un ingegnoso profano; ma una dimostrazione formale è decisamente ardua, e richiede di affrontare il problema da prospettive finora inusitate: un po' come ha fatto Perelman applicando il suo amato flusso di Ricci alla congettura di geometrizzazione di Thurston e quindi anche alla dimostrazione della congettura di Poincarè.
Ad esempio, si ritiene (e con solide ragioni) che una strada importante passi da una trattazione categoriale delle classi di complessità, che prenda le mosse dalla caratterizzazione logica di P e NP fatta in un lavoro seminale di Ron Fagin (IBM) degli anni '70.
@ david_e: perfettamente d'accordo, sarebbe una beffa per chi considera solo il lato pratico della questione. Ad esempio, PRIMES è in P, come hanno dimostrato i tre piccoli indiani AKS, ma le prestazioni sono decisamente penose (a meno che qualcuno non si butti sui primi di Sophie Germain, il che dovrebbe migliorare un po' lo status quo dell'algoritmo, peraltro già modificato dal notissimo Chris Caldwell).
"...una "dimostrazione" implicita sarebbe semplicemente l'ideazione di un algoritmo in tempo polinomiale per un problema NP...."
Mi pare di capire che il presupposto di partenza sia P=NP.
Con questa ipotesi di partenza viene naturale pensare che chiunque potrebbe trovare un algoritmo in tempo polinomiale per uno dei problemi NP-Completi.
Il fatto è che non sappiamo se P=NP oppure P diverso NP.
Quindi se fino ad ora non siamo riusciti a trovare nessun algoritmo per questi problemi non abbiamo neanche dimostrato che P sia diverso NP, ma se cosi fosse non troveremo mai(neanche per sbaglio) un algoritmo in tempo polinomiale.
Penso quindi che i "si ritiene" accademici siano dovuti a questo fatto; cioè che fino ad oggi ne ingegnosi profani ne illustri professori sono riusciti a trovare un algoritmo in tempo pol. per uno solo dei circa un migliaio di problemi che si ritengono essere NP-Completi....quindi delle due l'una: o questi problemi hanno tutti una soluzione polinomiale, e la cosa ci è sfuggita per secoli, oppure nessuno ne ha, e quindi richiedono veramente tempo esponenziale...
Mi pare di capire che il presupposto di partenza sia P=NP.
Con questa ipotesi di partenza viene naturale pensare che chiunque potrebbe trovare un algoritmo in tempo polinomiale per uno dei problemi NP-Completi.
Il fatto è che non sappiamo se P=NP oppure P diverso NP.
Quindi se fino ad ora non siamo riusciti a trovare nessun algoritmo per questi problemi non abbiamo neanche dimostrato che P sia diverso NP, ma se cosi fosse non troveremo mai(neanche per sbaglio) un algoritmo in tempo polinomiale.
Penso quindi che i "si ritiene" accademici siano dovuti a questo fatto; cioè che fino ad oggi ne ingegnosi profani ne illustri professori sono riusciti a trovare un algoritmo in tempo pol. per uno solo dei circa un migliaio di problemi che si ritengono essere NP-Completi....quindi delle due l'una: o questi problemi hanno tutti una soluzione polinomiale, e la cosa ci è sfuggita per secoli, oppure nessuno ne ha, e quindi richiedono veramente tempo esponenziale...
Per chiarire, anche per chi ci legge: il presupposto di partenza è unicamente $P\ sube \ NP$. Quel che si vuole mostrare è, alternativamente, che $P -= NP$ (e dunque ne è un sottoinsieme improprio), oppure che al contrario $NP\ /\ P \ !=\ \phi\ =>\ P\ sub\ NP$. In termini di puro principio, la prima tesi è relativamente facile da dimostrare (trovare l'algoritmo in P per un problema NP...), la seconda no.
La mia argomentazione è simmetrica a quella dei tanti "si ritiene che P != NP", e come quella della maggioranza poggia unicamente su una base epistemica (la caratterizzazione logica è un suggerimento che ho orecchiato dal mio capo, un logico, molti anni fa).
Non è chiaro se la questione in primo luogo sia decidibile. In seconda istanza rimane ancora da capire se trovare un algoritmo in tempo polinomiale per un problema NP-completo sia "semplicemente" un lavoraccio, o del tutto impossibile. Tuttavia, le probabilità di questi ultimi due casi sono identiche, a dispetto dell'apparenza: non cadiamo nella facile fallacia del "ci hanno lavorato in tanti e non hanno ancora mostrato che P=NP, nessuno ha ancora trovato un algoritmo in tempo polinomiale per un problema NP, dunque è PROBABILE che P != NP". L'esperienza dei problemi di Hilbert e in particolare dell'UTF, oltre al già ricordato Poincarè, dovrebbe insegnare qualcosa.
Ultima considerazione. Dimentichiamo per un attimo il professorone nell'esercizio delle sue funzioni o il volenteroso profano che fa il suo compito a casa così bene da trovare un algoritmo in P per SAT o quel che vogliamo, e concentriamoci sull'altro caso: un genio alla Grothendieck che riempie trecento pagine incomprensibili al 99,999% dei matematici e computer scientist e dimostra che $P -= NP$ utilizzando metodi superiori dell'algebra universale o chissà che altro. Da questo nulla segue concretamente, se non che in astratto esistono algoritmi in tempo polinomiale per noti problemi NP (il che è ben diverso dal saperne scrivere uno, o dall'avere un automa che prende in input un algoritmo NP e sputa fuori la relativa controparte P). Questo svuota ulteriormente di significato le obiezioni correnti vicine alla fallacia (mancanza di controesempi) di cui sopra.
Come informatico in servizio permanente effettivo sarei ovviamente interessato, nella pratica, a soluzioni in tempo polinomiale _E_ efficientemente computabili per i problemi con i BDD ed agli altri in NP. Come epistemologo della domenica, tuttavia, mi pare enormemente più importante la mera dimostrazione di coincidenza tra i due insiemi: di limitazioni pratiche e teoremi limitativi, seppure indorati e rifritti alla Chaitin (in soldoni "Sono una ricchezza, non un limite") mi pare che ne abbiamo già a sufficienza.
PS: la "cosa" alla quale fai riferimento nella tua bottom line, ovvero la eventuale presenza di soluzioni in tempo polinomiale ai problemi in NP, al più ci sfugge da qualche decennio, ossia da quando esiste l'informatica teorica (a rigore, da quando si parla ufficialmente di complessità computazionale). Sì, è arcinoto che il solito Gauss aveva anticipato perfino Cooley & Tuckey con l'algoritmo della FFT, e spulciando tomi polverosi si può sempre scoprire che chissà quale altro oscuro collaterale di Cardano o Niccolò Tartaglia aveva magari fatto patti col diavolo per inventare antenati di SAT o del TSP... ma questo implica, al più, che simili algoritmi non vengono fuori per sbaglio.
La mia argomentazione è simmetrica a quella dei tanti "si ritiene che P != NP", e come quella della maggioranza poggia unicamente su una base epistemica (la caratterizzazione logica è un suggerimento che ho orecchiato dal mio capo, un logico, molti anni fa
). Non è chiaro se la questione in primo luogo sia decidibile. In seconda istanza rimane ancora da capire se trovare un algoritmo in tempo polinomiale per un problema NP-completo sia "semplicemente" un lavoraccio, o del tutto impossibile. Tuttavia, le probabilità di questi ultimi due casi sono identiche, a dispetto dell'apparenza: non cadiamo nella facile fallacia del "ci hanno lavorato in tanti e non hanno ancora mostrato che P=NP, nessuno ha ancora trovato un algoritmo in tempo polinomiale per un problema NP, dunque è PROBABILE che P != NP". L'esperienza dei problemi di Hilbert e in particolare dell'UTF, oltre al già ricordato Poincarè, dovrebbe insegnare qualcosa.
Ultima considerazione. Dimentichiamo per un attimo il professorone nell'esercizio delle sue funzioni o il volenteroso profano che fa il suo compito a casa così bene da trovare un algoritmo in P per SAT o quel che vogliamo, e concentriamoci sull'altro caso: un genio alla Grothendieck che riempie trecento pagine incomprensibili al 99,999% dei matematici e computer scientist e dimostra che $P -= NP$ utilizzando metodi superiori dell'algebra universale o chissà che altro. Da questo nulla segue concretamente, se non che in astratto esistono algoritmi in tempo polinomiale per noti problemi NP (il che è ben diverso dal saperne scrivere uno, o dall'avere un automa che prende in input un algoritmo NP e sputa fuori la relativa controparte P). Questo svuota ulteriormente di significato le obiezioni correnti vicine alla fallacia (mancanza di controesempi) di cui sopra.
Come informatico in servizio permanente effettivo sarei ovviamente interessato, nella pratica, a soluzioni in tempo polinomiale _E_ efficientemente computabili per i problemi con i BDD ed agli altri in NP. Come epistemologo della domenica, tuttavia, mi pare enormemente più importante la mera dimostrazione di coincidenza tra i due insiemi: di limitazioni pratiche e teoremi limitativi, seppure indorati e rifritti alla Chaitin (in soldoni "Sono una ricchezza, non un limite") mi pare che ne abbiamo già a sufficienza.
PS: la "cosa" alla quale fai riferimento nella tua bottom line, ovvero la eventuale presenza di soluzioni in tempo polinomiale ai problemi in NP, al più ci sfugge da qualche decennio, ossia da quando esiste l'informatica teorica (a rigore, da quando si parla ufficialmente di complessità computazionale). Sì, è arcinoto che il solito Gauss aveva anticipato perfino Cooley & Tuckey con l'algoritmo della FFT, e spulciando tomi polverosi si può sempre scoprire che chissà quale altro oscuro collaterale di Cardano o Niccolò Tartaglia aveva magari fatto patti col diavolo per inventare antenati di SAT o del TSP... ma questo implica, al più, che simili algoritmi non vengono fuori per sbaglio.
"Andrea69":
Per chiarire, anche per chi ci legge: il presupposto di partenza è unicamente $P\ sube \ NP$. Quel che si vuole mostrare è, alternativamente, che $P -= NP$ (e dunque ne è un sottoinsieme improprio), oppure che al contrario $NP\ /\ P \ !=\ \phi\ =>\ P\ sub\ NP$. In termini di puro principio, la prima tesi è relativamente facile da dimostrare (trovare l'algoritmo in P per un problema NP...), la seconda no.
Be', in termini di puro principio, potrebbe essere di una enorme difficoltà anche provare che P=NP. In caso di una dimostrazione diretta, infatti, non basterebbe esibire un algoritmo polinomiale, bisognerebbe anche dimostrare che esso e' polinomiale: cio' potrebbe essere eccezionalmente difficile.
Basti pensare al caso dell'algoritmo deterministico di Miller-Rabin per la primalita': esso e' polinomiale, se nientemeno che l'ipotesi di Riemann e' vera. Quindi esibire l'algoritmo e' stato relativamente semplice, mentre studiarlo in termini di complessita' estremamente arduo.
In generale, stabilire la complessita' di un'algoritmo puo' essere incredibilmente difficile. A volte lo e' gia' dimostrare la terminazione.
Comunque, come ha notato Andrea, non e' vero che l'ipotesi $P=NP$ non e' quotata perche' finora i tentativi di trovare algoritmi polinomiali sono falliti (che vuol dire?); bensi' perche', a livello filosofico, sembra intrinsecamente piu' facile verificare che una dimostrazione matematica e' corretta, piuttosto che trovare tale dimostrazione. Perche' questo riguarda P vs NP: il salto che sembra esserci tra il "verificare", da un lato, e il "trovare", dall'altro.
Ho scritto per mio piacere un algoritmo per la risoluzione di K-SAT che a mio parere funziona in tempo polinomiale. Lo potete trovare al sito onthesat.org. Mi potete dare un'opinione?
Ciao,
Se vuoi proponi nel forum il tuo algoritmo.
"masspa":
Ho scritto per mio piacere un algoritmo per la risoluzione di K-SAT che a mio parere funziona in tempo polinomiale. Lo potete trovare al sito onthesat.org. Mi potete dare un'opinione?
Se vuoi proponi nel forum il tuo algoritmo.
@hamming_burst:ho guardato velocemente il pdf e si parla di programmazione dinamica..
Si, molto in breve descrivo come se N è il numero di clausole, esistano solo O(N^(2^K)) scelte che risultano scelte errate nella ricerca di una soluzione. Utilizzo poi la programmazione dinamica per tenere traccia di queste scelte. Questa e' la forma base dell'algoritmo la più lenta ma mi pare la più facile da capire.. dire di più non saprei in poche righe..
"masspa":
Si, molto in breve descrivo come se N è il numero di clausole, esistano solo O(N^(2^K)) scelte che risultano scelte errate nella ricerca di una soluzione. Utilizzo poi la programmazione dinamica per tenere traccia di queste scelte.
intuisco già delle possibili grandi limitazioni, ma penso sia interessante dargli una letta.
Se per grandi limitazioni intendi che anche se l'algoritmo risultasse corretto sarebbe in pratica non utilizzabile sono concorde con te, per K = 3 il tempo di esecuzione e' O(N^17). Pero come ho detto questa e' la forma che era piu' facile da dimostrare, e' possibile ridurre di moltissimo il tempo di esecuzione.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo