Onlangs is er een paperrondzwevend door Vinay Deolalikar bij HP Labs, die beweert te hebben bewezen dat P != NP.
Kan iemand uitleggen hoe dit bewijs werkt voor ons, minder wiskundig ingestelde mensen?
Antwoord 1, autoriteit 100%
Ik heb alleen het papier gescand, maar hier is een ruwe samenvatting van hoe het allemaal in elkaar steekt.
Van pagina 86 van de krant.
… polynomiale tijd
algoritmen slagen door achtereenvolgens
het probleem “opsplitsen” in
kleinere deelproblemen die zijn gekoppeld aan
elkaar via voorwaardelijke
onafhankelijkheid. Bijgevolg polynoom
tijdalgoritmen kunnen het niet oplossen
problemen in regimes waar blokken waarvan
volgorde is hetzelfde als de onderliggende
probleeminstantie vereist gelijktijdige
resolutie.
Andere delen van de paper laten zien dat bepaalde NP-problemen niet op deze manier kunnen worden opgebroken. Dus NP/= P
Een groot deel van het artikel wordt besteed aan het definiëren van voorwaardelijke onafhankelijkheid en het bewijzen van deze twee punten.
Antwoord 2, autoriteit 28%
Dick Lipton heeft een mooi blogberichtover de krant en zijn eerste indrukken ervan. Helaas is het ook technisch. Voor zover ik kan begrijpen, lijkt de belangrijkste innovatie van Deolalikar te zijn om enkele concepten uit de statistische fysica en de theorie van eindige modellen te gebruiken en deze aan het probleem te koppelen.
Ik ben met Rex M met deze, sommige resultaten, meestal wiskundige, kunnen niet worden uitgedrukt aan mensen die de technische beheersing missen.
Antwoord 3, autoriteit 16%
Ik vond dit leuk ( http://www.newscientist.com/article/dn19287-p–np-its-bad-news-for-the-power-of-computing.html):
Zijn argument draait om een bepaalde taak, het Booleaanse vervulbaarheidsprobleem, dat zich afvraagt of een verzameling logische uitspraken allemaal tegelijkertijd waar kan zijn of dat ze elkaar tegenspreken. Dit staat bekend als een NP-probleem.
Deolalikar beweert te hebben aangetoond dat
er is geen programma dat kan voltooien
het snel van de grond af, en dat het
is daarom geen P-probleem. Zijn
argument omvat het ingenieuze gebruik van
statistische fysica, zoals hij gebruikt a
wiskundige structuur die volgt
veel van dezelfde regels als een willekeurige
fysiek systeem.
De effecten van het bovenstaande kunnen behoorlijk groot zijn:
Als het resultaat blijft bestaan, zou dat bewijzen
dat de twee klassen P en NP dat niet zijn
identiek zijn, en strenge beperkingen opleggen aan:
wat computers kunnen bereiken –
wat inhoudt dat veel taken kunnen zijn
fundamenteel, onherleidbaar complex.Voor sommige problemen – waaronder
factorisatie – het resultaat niet
duidelijk zeggen of ze kunnen worden opgelost
snel. Maar een enorme subklasse van
problemen genaamd “NP-compleet” zouden zijn
gedoemd. Een bekend voorbeeld is de
handelsreiziger probleem – vinden
de kortste route tussen een set van
steden. Dergelijke problemen kunnen worden gecontroleerd
snel, maar als P ≠ NP dan is er
geen computerprogramma dat kan voltooien
ze snel helemaal opnieuw.
Antwoord 4, autoriteit 9%
Dit is mijn begrip van de bewijstechniek: hij gebruikt logica van de eerste orde om alle polynomiale tijdalgoritmen te karakteriseren, en laat vervolgens zien dat voor grote SAT-problemen met bepaalde eigenschappen geen polynomiale tijdalgoritme hun vervulbaarheid kan bepalen.
Antwoord 5, autoriteit 5%
Een andere manier om erover na te denken, die misschien helemaal verkeerd is, maar mijn eerste indruk is als ik het bij de eerste doorgang lees, is dat we denken aan het toewijzen/opruimen van termen in circuittevredenheid als het vormen en breken van clusters van ‘geordende structuur’, en dat hij vervolgens statistische fysica gebruikt om aan te tonen dat er niet genoeg snelheid is in de polynomiale bewerkingen om die bewerkingen uit te voeren in een bepaalde “faseruimte” van bewerkingen, omdat deze “clusters” uiteindelijk te ver weg zijn uit elkaar.
Antwoord 6, autoriteit 2%
Dergelijk bewijs zou alle klassen van algoritmen moeten dekken, zoals continue globale optimalisatie.
Bij het 3-SAT-probleemmoeten we bijvoorbeeld variabelen evalueren om aan alle alternatieven van triples van deze variabelen of hun ontkenningen te voldoen. Kijk of x OR yveranderd kan worden in optimaliseren
((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)
en analoog zeven termen voor alternatief van drie variabelen.
Het vinden van het globale minimum van een som van dergelijke veeltermen voor alle termen zou ons probleem oplossen. (bron)
Het gaat van standaard combinatorische technieken naar de continue wereld met behulp van_gradient-methoden, lokale minims-verwijderingsmethoden, evolutionaire algoritmen. Het is een heel ander koninkrijk – numerieke analyse – ik geloof niet dat zo’n bewijs echt (?) kan dekken
Antwoord 7
Het is vermeldenswaard dat met bewijzen “de duivel in de details zit”. Het overzicht op hoog niveau is duidelijk zoiets als:
Een soort relatie
tussen items, laat zien dat dit
relatie impliceert X en dat
impliceert Y en dus is mijn argument
weergegeven.
Ik bedoel, het kan zijn via Inductieof een andere vorm van bewijzen, maar wat ik zeg is dat het overzicht op hoog niveau nutteloos is. Het heeft geen zin om het uit te leggen. Hoewel de vraag zelf betrekking heeft op informatica, kunt u deze het beste aan wiskundigen overlaten (ze vonden het zeker ongelooflijk interessant).