den 24.maj 2000 kom Clay Mathematics Institute op med syv matematiske problemer, for hvilke løsningen på et hvilket som helst af problemet vil tjene US $1.000.000 belønning for solver. Kendt som Millennium Problems, indtil videre, kun et af de syv problemer er løst indtil dato.

vil du lave en million dollar, prøv at løse en fra denne liste. Det er de problemer, der er anført for en million dollar præmie belønning.,

  1. Yang–Mills og Masse Hullet
  2. Riemann Hypotese
  3. P vs NP-Problem
  4. Navier–Stokes Ligning
  5. Hodge Formodningen
  6. Poincarés Formodning
  7. Birch og Swinnerton-Dyer Formodningen

Okay, lad os være realistiske her, disse problemer er her for en grund. Du gættede det rigtigt, disse problemer er svære at løse. Faktisk er de dybe og virkelig vanskelige, ikke kun for at løse dem, men endda for at forstå problemformuleringen. De fleste af de nævnte problemer har brug for lydfagskendskab og analyse selv for at forstå spørgsmålet.,

Poincar.formodninger er det eneste problem, der er løst blandt disse syv spørgsmål. Dette problem er fra topologi domæne, der beskæftiger sig med, hvordan objekter passer sammen og deres form i rummet. Dette problem var specifikt relateret til kugler.

i 1904 spurgte den franske matematiker Henri Poincar., om den tredimensionelle sfære er karakteriseret som den unikke simpelthen forbundne tre manifold. Dette spørgsmål, Poincar .s formodninger, var et særligt tilfælde af Thurston ‘ s geometrizationation formodninger., Perelmans bevis fortæller os, at hver tre manifold er bygget fra et sæt standardstykker, hver med en af otte velkendte geometrier.

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

Komplicerede ting uhmmm! Lad os diskutere lidt mere af dette, før vi går videre til P versus NP.Henri Poincar .s, erklærede problemet i 1904, som i meget generelle, at hvis du har et objekt med ingen huller og dens størrelse er forholdsvis lille og finite så er det en kugle (eller kan gøres til en kugle). Dette er ikke kun for 3 dimension, men for alle dimensioner.,

men udsagnet blev ikke bevist for fjerde dimension, indtil Grigori Perelman kom med løsningen i 2003, baseret på arbejde af Richard Hamilton.

Hvis du er interesseret, er her hvad en million dollar løsning ser ud: https://arxiv.org/abs/math/0211159

Grigori Perelman blev tildelt en million dollar og fields-medalje, både af hvor han faldt.

Hvad skal man sige? Nogle af os kan lide at løse problemer, bare for sjov at løse det.

lykke nyder processen!,

p versus NP er det seneste problem, der blev opført i Millennium Problemlisten. Dette problem blev angivet i 1971.

den præcise opgørelse af P versus NP problem blev indført i 1971 af Stephen Cook i hans skelsættende papir “kompleksiteten af sætning bevise procedurer”.

for korrekt at forstå P versus NP-problemet er grundlæggende viden om beregningskompleksitet et must. Faktisk P vs NP er det mest forventede problem for løsning inden for datalogi., Så et godt greb om, hvordan dette problem påvirker computerlandskabet, hjælper os med at fordøje dette problem.

Hvis du er ny med emnet beregningskompleksitet eller kompleksitet generelt, vil jeg meget opfordre dig til at se på min tidligere historie om “hvad er Beregningskompleksitet?”

de fleste af problemerne i beregningsrummet kan reduceres til et beslutningsproblem. Det betyder problemer, hvor svaret er enten ja eller nej.

så lad os komme tilbage til spørgsmålet om, hvad der er P? og hvad er NP?,

både P og NP kan betragtes som et sæt problemer, der er grupperet ud fra, hvor vanskeligt det er at løse og evaluere løsningen. Udtrykket vanskeligt er især vigtigt i denne sammenhæng, hvilket dybest set betyder, hvor beregningsmæssigt intensivt et problem er at løse og kontrollere løsningen.

for eksempel overveje problemet med multiplikation. Dette er relativt et let problem at løse. Ikke kun at dette problem er let at løse, dette kan også verificeres med samme lethed bare ved at multiplicere tallene., Dybest set, ethvert problem, der kan løses i polynomiel tid og resultatet, som kan blive kontrolleret i polynomiel tid, og det er under det komplekse sæt af P.

P ( polynomiel tid), som indeholder alle afgørelse problemer, der kan løses af en deterministisk Turing maskine ved hjælp af et polynomium mængden af beregningen tid, eller polynomiel tid.

Der er dette andet sæt problemer, der kan verificeres i polynomisk tid, men for at løse dette problem vil det tage mere end polynomisk tid. For eksempel, lad os tage Sudoku for eksempel., I betragtning af at vi har en løsning til ethvert spil, kan vi let verificere det. Det betyder, at vi kan gøre verifikation del i polynomiel tid. Men for at løse puslespillet har vi brug for mere tid. Også som antallet af Net stiger, kompleksiteten af at finde en løsning stiger eksponentielt.

NP (nondeterministisk polynomitid) er en kompleksitetsklasse, der bruges til at klassificere beslutningsproblemer. NP er det sæt af beslutningsproblemer, som problemforekomsterne, hvor svaret er “ja”, har bevis, der kan verificeres i polynomisk tid., (bare lov til at være polynomially store, ikke større)

Interessant punkt at bemærke er, at hvert problem, der er i P er også en del af NP. Men dette kan eller måske ikke være skruestik-versa. Her er hvor forskningen tankegang pitch-in. Så løsningen på NP-problemer er langsom, men de kan verificeres hurtigt. Kan vi forbedre hastigheden for løsningen?

lad os se på primalitetsproblemet. En primalitetstest er en algoritme til bestemmelse af, om et inputnummer er prime.,

Givet naturligt tal n, er n prime?

Dette problem blev anset for at være et problem i NP delmængde indtil AKS oprindelighed test viste, at dette problem er under P.,

AKS oprindelighed test (også kendt som Agrawal–Kayal–Saxena oprindelighed test og cyclotomic AKS-test) er en deterministisk oprindelighed-som bevis algoritme skabt og udgivet af Manindra Agrawal, Neeraj Kayal, og Nitin Saxena, dataloger ved Indian Institute of Technology, Kanpur, 6 August, 2002, i en artikel med titlen “PRIMES is in P”

Så er der en mulighed for, at alle problemer i NP kan løses i P kompleksitet?, Eller er der sæt af problemer, der altid vil være svært at finde løsning for at gøre P og NP altid forblive adskilt? Svaret er ukendt. Det er faktisk problemet med millioner dollars.

hvis det er let at kontrollere, at en løsning på et problem er korrekt, er det også let at løse problemet?

typisk for NP problemer er, at Hamiltonian Path Problem: givet n byer at besøge, Hvordan kan man gøre dette uden at besøge en by to gange? Hvis du giver mig en løsning, kan jeg nemt kontrollere, at det er korrekt. Men jeg kan ikke så let finde en løsning.,

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

Nogle problemer i NP kan grupperes som NP-komplet. Dette er en gruppe af problemer, hvor hvis en hurtig løsning på et af et problem er fundet, kan vi løse en gruppe af problemer i samme sæt af kompleksitet med lethed.

Et problem er NP-komplet, når det kan løses ved en begrænset klasse af brute force søgealgoritmer, og det kan bruges til at simulere et andet problem med en lignende algoritme.,

NP-fuldstændighed er især vigtigt i P versus NP diskussion som en løsning i P-tid, for et problem i NP-komplet sæt beviser, at hele den kompleksitet, der vil bryde sammen. Hvilket vil betyde, at NP-Complete = NP = p

et NP-complete problem vil være i NP og vil være i NP-Hard, hvilket betyder, at dette problem er mindst lige så hårdt som ethvert problem i NP, som illustreret nedenfor.,

Et problem er NP-hårdt, hvis en algoritme til løsning af det kan oversættes til én for at løse eventuelle NP-problem (nondeterministic polynomial tid) problem. NP-hard betyder derfor “mindst lige så hårdt som ethvert NP-problem”, selvom det faktisk kan være sværere.

Der er problemer uden for NP, som er svært at lave en løsning, der på samme tid svært at kontrollere løsningen, for eksempel overveje skak., I betragtning af enhver position på et bord er det svært at finde det bedste næste træk, det er også svært at verificere det næste træk for at være nøjagtigt eller ej. Dette problem er i E .p (eksponentiel tidskompleksitet)og måske uden for NP.

de fleste forskere inden for beregningskompleksitetsteori mener, at P ikke er lig med NP. Begivenhed selvom der er mange interessante problemer i NP, der påvirker vores dag i dag liv som optimering problemer. En løsning på et NP-komplet problem som proteinfoldning betyder, at vi vil være meget tættere på at finde ud af kuren mod kræft., Også, hvis P=NP så kan vi finde den offentlige nøgle kryptografi at blive brudt, da det afhænger af heltal faktorisering, som er et problem i NP, og vi er afhængige af denne hårdhed til løsning for de fleste af vores kryptografi. Så implikationer af at bevise N=NP er blandet.

Der var meget forskning i at bevise enten P = NP eller vise-versa. Men dette problem i sig selv synes at være NP-hard (bare sarkastisk her), da der ikke er nogen afgørende resultater fra nu af. Men verden vil være et langt mere interessant sted, hvis nogen kan bevise, at P=NP., Men fra nu af tænker de fleste af de veluddannede mennesker fra marken ellers.

I sin blog, der er berømt forsker beregningsmæssige kompleksitet teori, Scott Aaronson fastslår, at

Hvis P = NP, så ville verden være et helt anderledes sted, end vi normalt antager, at det at være. Der ville ikke være nogen særlig værdi i “kreative Spring”, ingen grundlæggende kløft mellem at løse et problem og genkende løsningen, når den først er fundet., Alle, der kunne værdsætte en symfoni ville være Mozart; alle, der kan følge en trin-for-trin argument ville være, Gauss; alle, der kunne genkende en god investering strategi ville være Warren Buffett.

tak for din tid.

redigeret af Ashok Jeevan