På Mai 24, 2000, Clay Mathematics Institute kom opp med syv matematiske problemer, som løsningen for noen av problemet vil tjene US $1 000 000 i lønn for en problemløser. Kjent som den Millennium Problemer, så langt, er bare en av de sju problemene er løst til dato.

Ønsker å gjøre en million dollar, kan du prøve å løse en fra denne listen. Disse er problemene som er oppført for en million dollar i premie belønning.,

  1. Yang–Mills og Masse Gap
  2. Riemann-Hypotesen
  3. P vs NP Problem
  4. Navier–Stokes Ligning
  5. Hodge-Formodningen
  6. Poincaré-Formodningen
  7. Bjørk og Swinnerton-Dyer-Formodningen

Okay, la oss være realistiske her, disse problemene er her for en grunn. Du gjettet det rett, disse problemene er vanskelige å løse. I-faktisk at de er dype og veldig vanskelig, ikke bare for å løse dem, men også for å forstå problemet uttalelse. De fleste av problemene som er oppført trenger lyd fagkunnskap og analyse selv å forstå spørsmålet.,

Poincaré-Formodningen er det eneste problemet som er løst blant disse syv spørsmål. Dette problemet er fra topologi domene, som omhandler hvordan objekter som passer sammen og formen på plass. Dette problemet er spesielt knyttet til kuler.

I 1904 den franske matematikeren Henri Poincaré spurt om den tre-dimensjonale sfæren er karakterisert som den unike rett og slett koblet tre manifold. Dette spørsmålet, Poincaré-formodningen, var et spesielt tilfelle av Thurston er geometrization gjetninger., Perelman er bevis forteller oss at hver tre manifold er bygd opp av et sett av standard deler, hver med ett av åtte godt forstått geometrier.

Se: https://www.claymath.org/millennium-problems

Kompliserte ting uhmmm! Kan diskutere litt mer av dette før du går videre til P versus NP.

Henri Poincaré, uttalte problemet i 1904, som i svært generelle sier at, hvis du har en gjenstand uten hull, og størrelsen er ganske liten, og endelig så det er en sfære (eller kan bli gjort om til en sfære). Dette er ikke bare for 3 dimensjon, men for alle dimensjoner.,

Men uttalelsen ble ikke påvist for fjerde dimensjon, til Grigori Perelman kom opp med løsningen i 2003, basert på arbeider av Richard Hamilton.

Hvis du er interessert, her er hva en million dollar løsning ser ut som: https://arxiv.org/abs/math/0211159

Grigori Perelman ble tildelt én million dollar og fields-medaljen, både som han har avslått.

Hva du skal si? Noen av oss liker å løse problemer, bare for moro av å løse det.

Lykke er å nyte prosessen!,

P versus NP er det siste problemet som ble oppført i Millennium-Problem-listen. Dette problemet ble nevnt i 1971.

presis redegjørelse av P versus NP problemet ble introdusert i 1971 av Stephen Cook i sin banebrytende papir «kompleksiteten av teorem som beviser prosedyrer».

for å riktig forstå versus S NP-problem, grunnleggende kunnskap om computational kompleksitet er et must. I-fakta P vs NP er den mest etterlengtede problem for løsning i informatikk., Så, et godt grep om hvordan dette problemet påvirker databehandling landskapet vil hjelpe oss til å fordøye dette problemet.

Hvis du er ny til temaet i beregningsorientert kompleksitet eller kompleksitet generelt, vil jeg sterkt oppfordre deg til å ta en titt inn i mitt forrige historie på «Hva er Beregningsorientert Kompleksitet?»

de Fleste av problemene i beregningsorientert plass kan bli redusert til en beslutning om problemet. Det betyr at problemer der svaret er enten JA eller NEI.

Så kan du komme tilbake til spørsmålet om hva som er P? og hva er NP?,

Både P og NP kan betraktes som et sett av problemer som er gruppert basert på hvor vanskelig det er å løse og evaluere løsningen. Begrepet vanskelig er spesielt viktig i denne sammenhengen, som i utgangspunktet betyr at hvordan beregninger intensiv et problem å løse, og sjekk løsningen.

For eksempel, tenk problemet med multiplikasjon. Dette er en relativt enkelt problem å løse. Ikke bare at dette problemet er lett å løse, dette kan også bekreftes med samme letthet bare ved å multiplisere tall., I utgangspunktet, noen problem som kan løses i polynomisk tid, og resultatet kan bli bekreftet i polynomisk tid, er under kompleksiteten sett av S.

P ( polynomisk tid) inneholder alle beslutning om problemer som kan løses ved hjelp av en deterministisk Turing-maskinen ved hjelp av en polynomisk mengde beregning tid, eller polynomisk tid.

Det er dette andre sett av problemer som kan bli bekreftet i polynomisk tid, men, for å løse dette problemet vil det ta mer enn polynomisk tid. For eksempel, la oss ta Sudoku for eksempel., Gitt at vi har en løsning for alle spill, kan vi bekrefte det enkelt. Dette betyr at vi kan gjøre bekreftelse del i polynomisk tid. Men for å løse puslespill, vi trenger mer tid. Også som nummer av nett øke kompleksiteten av å finne en løsning øker eksponentielt.

NP (nondeterministic polynom-tid) er en kompleksitet klasse brukes til å klassifisere beslutning problemer. NP er det satt av vedtak problemer som problemet tilfeller, der svaret er «ja», har etterprøvbare bevis i polynomisk tid., (bare lov til å være polynomially stort, er ikke større)

Interessant punkt å merke seg er at ethvert problem som er i P-er også en del av NP. Men dette kan eller kan ikke være skrustikke versa. Her er der forskning tankegangen pitch-i. Så, løsning for NP-problemer er treg, men de kan verifiseres fort. Kan vi forbedre hastigheten for løsningen?

Kan se inn i primality problem. En primality test er en algoritme for å avgjøre om en inngang nummer er prime.,

Gitt naturlig tall n er n prime?

Dette problemet ble ansett for å være et problem i NP delsett til AKS primality test viste at dette problemet er under S.,

AKS primality test (også kjent som Agrawal–Kayal–Saxena primality test og cyclotomic AKS-test) er en deterministisk primality-beviser algoritme opprettet og publisert av Manindra Agrawal, Neeraj Kayal, og Nitin Saxena, datamaskinen forskere ved Indian Institute of Technology Kanpur, August 6, 2002, i en artikkel med tittelen «PRIMTALL er i P»

Så, er det en mulighet for at alle problemer i NP kan løses i S kompleksitet?, Eller er det sett av problemer som alltid vil være vanskelig å finne løsning for å gjøre P og NP alltid holde atskilt? Svaret er ukjent. I virkeligheten, det er millioner dollar problem.

Hvis det er lett å sjekke at en løsning på et problem er riktig, er det også lett å løse problemet?

Typisk for NP-problemer er at av Hamiltonian Banen Problem: gitt N byer å besøke, hvordan kan man gjøre dette uten å besøke en by to ganger? Hvis du gir meg en løsning, jeg kan lett kontrollere at den er riktig. Men jeg kan ikke så lett å finne en løsning.,

Se: https://www.claymath.org/millennium-problems/p-vs-np-problem

Noen problemer i NP kan grupperes som NP fullstendig. Dette er en gruppe av problemet der hvis en rask løsning på noen av ett problemet er funnet kan vi løse en gruppe av problemet i samme sett av kompleksitet med letthet.

Et problem er NP-komplett når det kan løses ved at en begrenset klasse av brute force søk algoritmer og det kan brukes til å simulere alle andre problem med en lignende algoritme.,

NP fullstendighet er spesielt viktig i S versus NP diskusjon som en løsning i P-tid, for et problem i NP-komplett sett beviser at hele kompleksiteten sett vil kollapse. Noe som vil bety at NP-Komplett = NP = P

Et NP-komplett problem vil være i NP og vil være i NP-Hard som mener at dette problemet er minst like vanskelig som alle problemer i NP, som illustrert nedenfor.,

Et problem er NP-vanskelig hvis en algoritme for å løse det kan være oversatt til for å løse alle NP-problem (nondeterministic polynomisk tid) problem. NP-hard betyr derfor «minst like hardt som alle NP-problem,» selv om det kan faktisk være vanskeligere.

Det er problemer utenfor NP som er vanskelig å lage en løsning, samtidig vanskelig å kontrollere løsning som godt, for eksempel, bør du vurdere sjakk., Gitt en hvilken som helst posisjon på et brett det er vanskelig å finne de beste neste trekk også det er vanskelig å kontrollere neste trekk for å være nøyaktig eller ikke. Dette problemet er i EXP (Eksponensiell tid kompleksitet)og kanskje utenfor NP.

de Fleste av forskerne innen beregningsorientert kompleksitet teori mener at P er ikke lik for å NP. Arrangementet selv om det er mange interessante problemer i NP som påvirker vår dag i dag livet som optimalisering problemer. En løsning på en NP Komplett problem som protein folding betyr at vi vil være mye nærmere å finne ut kur for kreft., Også, hvis P=NP så vi kan finne den offentlig-nøkkel kryptografi for å bli brutt da det avhenger av heltall factorisation som er et problem i NP og vi er avhengig av denne hardhet til løsning for de fleste av våre kryptografi. Så, implikasjoner av beviser N=NP er blandet.

Det var mye forskning sette inn beviser enten P = NP eller skrustikke versa. Men dette problemet i seg selv synes å være NP-hard (bare å være sarkastisk her) så det er ingen konkrete resultater av nå. Men verden vil være en langt mer interessant sted hvis noen kan bevise at P=NP., Men som nå, de fleste av de godt utdannede mennesker fra feltet mener noe annet.

I bloggen sin, som er berømt forsker computational kompleksitet teori, Scott Aaronson sier at,

Hvis P = NP, da ville verden bli et svært annerledes sted enn vi vanligvis antar at det skal være. Det ville ikke være noen spesiell verdi i «kreative sprang,» ingen fundamental gap mellom å løse et problem, og erkjenner løsning når den er funnet., Alle som kunne sette pris på en symfoni ville være Mozart; alle som kunne følge en steg-for-trinn-argumentet ville være Gauss; alle som kunne gjenkjenne en god investering strategi ville være Warren Buffett.

Takk for din tid.

Redigert av Ashok Jeevan