Il 24 maggio 2000, Clay Mathematics Institute si avvicinò con sette problemi matematici, per i quali, la soluzione per qualsiasi problema guadagnerà US reward 1.000.000 ricompensa per il risolutore. Notoriamente conosciuti come i problemi del Millennio, finora, solo uno dei sette problemi è risolto fino ad oggi.
Vuoi fare un milione di dollari, prova a risolverne uno da questa lista. Questi sono i problemi elencati per un milione di dollari premio premio.,
- Yang–Mills e Gap di Massa
- Ipotesi di Riemann
- P vs NP Problema
- Navier–Stokes Equazione
- Congettura di Hodge
- Congettura di Poincaré
- Birch e Swinnerton-Dyer Congettura
va Bene, cerchiamo di essere realistici qui, questi problemi sono qui per un motivo. Hai indovinato bene, questi problemi sono difficili da risolvere. In realtà sono profonde e davvero difficile, non solo per risolverli, ma anche per capire la dichiarazione problema. La maggior parte dei problemi elencati avrà bisogno di una solida conoscenza e analisi del soggetto anche per capire la domanda.,
La congettura di Poincaré è l’unico problema risolto tra queste sette domande. Questo problema proviene dal dominio topologia, che si occupa di come gli oggetti si incastrano e della loro forma nello spazio. Questo problema era specificamente correlato alle sfere.
Nel 1904 il matematico francese Henri Poincaré chiese se la sfera tridimensionale è caratterizzata come l’unico collettore semplicemente collegato tre. Questa domanda, la congettura di Poincaré, era un caso speciale della congettura di geometrizzazione di Thurston., La prova di Perelman ci dice che ogni tre manifold è costruito da un insieme di pezzi standard, ognuno con una delle otto geometrie ben comprese.
Fare riferimento:https://www.claymath.org/millennium-problems
Roba complicata uhmmm! Discutiamo un po ‘ di più di questo prima di passare a P contro NP.
Henri Poincaré, ha dichiarato il problema nel 1904, che in termini molto generali afferma che, se hai un oggetto senza buchi e la sua dimensione è abbastanza piccola e finita, allora è una sfera (o può essere trasformata in una sfera). Questo non è solo per 3 dimensioni, ma per tutte le dimensioni.,
Ma la dichiarazione non è stata dimostrata per la quarta dimensione, fino a quando Grigori Perelman non ha trovato la soluzione nel 2003, basata sul lavoro di Richard Hamilton.
Se sei interessato, ecco come appare una soluzione da un milione di dollari:https://arxiv.org/abs/math/0211159
Grigori Perelman ha ricevuto una medaglia da un milione di dollari e fields, entrambe declinate.
Cosa dire? Ad alcuni di noi piace risolvere i problemi, solo per il divertimento di risolverli.
La felicità sta godendo il processo!,
P versus NP è il problema più recente che è stato elencato nella lista dei problemi del Millennio. Questo problema è stato dichiarato nel 1971.
L’affermazione precisa del problema P contro NP è stata introdotta nel 1971 da Stephen Cook nel suo documento seminale “The complexity of theorem proving procedures”.
Per comprendere correttamente il problema P rispetto a NP, la conoscenza di base della complessità computazionale è un must. Infatti P vs NP è il problema più atteso per la soluzione in informatica., Quindi, una buona presa su come questo problema influisce sul panorama informatico ci aiuterà a digerire questo problema.
Se sei nuovo al tema della complessità computazionale o della complessità in generale, ti incoraggerò vivamente a dare un’occhiata alla mia storia precedente su “Cos’è la complessità computazionale?”
La maggior parte dei problemi nello spazio computazionale può essere ridotta a un problema decisionale. Ciò significa problemi in cui la risposta è SÌ o NO.
Quindi torniamo alla domanda su cosa sia P? e cos’è NP?,
Sia P che NP possono essere considerati come un insieme di problemi raggruppati in base a quanto sia difficile risolvere e valutare la soluzione. Il termine difficile è particolarmente importante in questo contesto, il che significa fondamentalmente che un problema computazionalmente intensivo è quello di risolvere e controllare la soluzione.
Ad esempio, considera il problema della moltiplicazione. Questo è relativamente un problema facile da risolvere. Non solo che questo problema è facile da risolvere, questo può anche essere verificato con la stessa facilità semplicemente moltiplicando i numeri., Fondamentalmente, qualsiasi problema che può essere risolto in tempo polinomiale e il cui risultato può essere verificato in tempo polinomiale, è sotto la complessità set di P.
P ( tempo polinomiale) contiene tutti i problemi di decisione che può essere risolto da una macchina di Turing deterministica utilizzando un polinomio quantità di tempo di calcolo, o in tempo polinomiale.
C’è questo altro insieme di problemi che possono essere verificati in tempo polinomiale ma, per risolvere questo problema, ci vorrà più del tempo polinomiale. Ad esempio, prendiamo Sudoku per esempio., Dato che abbiamo una soluzione per qualsiasi gioco, possiamo verificarlo facilmente. Ciò significa che possiamo fare la parte di verifica in tempo polinomiale. Ma per risolvere il puzzle, abbiamo bisogno di più tempo. Inoltre, con l’aumentare del numero di griglie, la complessità di trovare una soluzione aumenta esponenzialmente.
NP (nondeterministic polynomial time) è una classe di complessità utilizzata per classificare i problemi decisionali. NP è l’insieme di problemi decisionali per i quali le istanze del problema, in cui la risposta è “sì”, hanno prove verificabili in tempo polinomiale., (solo permesso di essere polinomialmente grande, non più grande)
Il punto interessante da notare è che ogni problema che si trova in P fa anche parte di NP. Ma questo potrebbe o non potrebbe essere viceversa. Qui è dove la mentalità di ricerca pitch-in. Quindi, la soluzione per i problemi NP è lenta ma può essere verificata velocemente. Possiamo migliorare la velocità per la soluzione?
Consente di esaminare il problema della primalità. Un test di primalità è un algoritmo per determinare se un numero di input è primo.,
Dato il numero naturale n, è n primo?
Questo problema è stato considerato un problema nel sottoinsieme NP fino a quando il test di primalità AKS ha dimostrato che questo problema è sotto P.,
L’AKS test di primalità (noto anche come Agrawal–Kayal–Saxena test di primalità e cyclotomic AKS test) è un deterministica di primalità-dimostrando algoritmo creato e pubblicato da Manindra Agrawal, Neeraj Kayal, e Nitin Saxena, esperti di informatica presso l’Istituto Indiano di Tecnologia di Kanpur, il 6 agosto 2002, in un articolo dal titolo “numeri PRIMI è in P”
Così, c’è una possibilità che tutti i problemi in NP può essere risolto in P complessità?, O c’è una serie di problemi che saranno sempre difficili da trovare soluzione per rendere P e NP sempre separati? La risposta è sconosciuta. In realtà, questo è il problema milioni di dollari.
Se è facile verificare che una soluzione a un problema sia corretta, è anche facile risolvere il problema?
Tipico dei problemi NP è quello del problema del percorso Hamiltoniano: date N città da visitare, come si può fare questo senza visitare una città due volte? Se mi dai una soluzione, posso facilmente verificare che sia corretta. Ma non riesco così facilmente a trovare una soluzione.,
Riferimento:https://www.claymath.org/millennium-problems/p-vs-np-problem
Alcuni problemi in NP possono essere raggruppati come NP completi. Questo è un gruppo di problemi in cui se viene trovata una soluzione rapida a uno qualsiasi dei problemi, possiamo risolvere facilmente un gruppo di problemi nello stesso insieme di complessità.
Un problema è NP-completo quando può essere risolto da una classe ristretta di algoritmi di ricerca a forza bruta e può essere utilizzato per simulare qualsiasi altro problema con un algoritmo simile.,
La completezza NP è particolarmente importante nella discussione P rispetto a NP come soluzione nel tempo P, poiché un problema in NP-complete set dimostra che l’intero set di complessità collasserà. Ciò significa che NP-Complete = NP = P
Un problema NP-completo sarà in NP e sarà in NP-Hard il che significa che questo problema è almeno duro come qualsiasi problema in NP, come illustrato di seguito.,
Un problema è NP-difficile, se un algoritmo per la risoluzione di esso può essere tradotto in uno per la risoluzione di eventuali NP-problema (non deterministica in tempo polinomiale) problema. NP-hard significa quindi “almeno duro come qualsiasi problema NP”, anche se potrebbe, in realtà, essere più difficile.
Ci sono problemi al di fuori di NP che sono difficili da fare una soluzione allo stesso tempo difficile da controllare anche la soluzione, ad esempio, considera gli scacchi., Data qualsiasi posizione su una tavola è difficile trovare la migliore prossima mossa inoltre è difficile verificare la prossima mossa per essere precisi o meno. Questo problema è in EXP (Exponential time complexity)e forse al di fuori di NP.
La maggior parte dei ricercatori nel campo della teoria della complessità computazionale ritiene che P non sia uguale a NP. Evento anche se ci sono molti problemi interessanti in NP che influenzano la nostra vita di oggi come problemi di ottimizzazione. Una soluzione a un problema NP Completo come il ripiegamento delle proteine significa che saremo molto più vicini a capire la cura per il cancro., Inoltre, se P=NP, potremmo trovare la crittografia a chiave pubblica interrotta in quanto dipende dalla fattorizzazione intera che è un problema in NP e dipendiamo da questa durezza per la soluzione per la maggior parte della nostra crittografia. Quindi, le implicazioni di dimostrare N = NP sono miste.
Ci sono state molte ricerche per dimostrare P = NP o vise-versa. Ma questo problema sembra essere NP-difficile (solo essere sarcastico qui) in quanto non ci sono risultati conclusivi al momento. Ma il mondo sarà un posto molto più interessante se qualcuno può dimostrare che P=NP., Ma a partire da ora, la maggior parte delle persone ben istruite dal campo la pensa diversamente.
Nel suo blog, famoso ricercatore computational complexity theory, Scott Aaronson afferma che,
Se P = NP, allora il mondo sarebbe un posto profondamente diverso da quello che di solito supponiamo che sia. Non ci sarebbe alcun valore speciale nei “salti creativi”, nessun divario fondamentale tra la risoluzione di un problema e il riconoscimento della soluzione una volta trovata., Tutti coloro che potrebbero apprezzare una sinfonia sarebbe Mozart; tutti coloro che potrebbero seguire un argomento passo-passo sarebbe Gauss; tutti coloro che potrebbero riconoscere una buona strategia di investimento sarebbe Warren Buffett.
Grazie per il vostro tempo.
A cura di Ashok Jeevan
Lascia un commento