Dr G
2011-01-12 03:43:30 UTC
Ik vraag me af of iemand een roman heeft geschreven die zich afspeelt in een universum waarin P = NP , in het geval dat er meer dan één is, welke de eerste was?
In dit universum zouden alle problemen die konden worden geverifieerd in polynoomtijd (NP) (gegeven de oplossing) ook kunnen worden opgelost in polynoomtijd (P).
om een goede reden, zou ik me voorstellen. Ik kan de dialoog nu zien.
Greg Egan schreef Dark integers en Luminous die gaan over berekenbaarheid en complexiteit in een pure algebra-omgeving. Als dat kan werken, kan ook een roman over P = NP :)
Geen roman, maar Russell Impagliazzo (een toponderzoeker op het gebied van complexiteitstheorie) schreef een korte paper waarin hij vijf werelden beschrijft waarin dergelijke dingen gebeuren (het Algorithmica-universum heeft P = NP, Cryptomania heeft cryptografie met openbare sleutels gegarandeerd, enz.). Ik dacht dat ik het zou vermelden voor het geval je nieuwsgierig bent naar een meer theoretisch standpunt over hoe een wereld met P = NP eruit zou zien. http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html
Dr. G +1, maar ik weet niet zeker welke versies van Egan's korte verhalen je hebt gelezen: P maar ik nam aan dat waarheidswaarden van rekenkundige uitspraken zich gedroegen als de spin van een kwantumdeeltje, en de berekening van wiskundige resultaten waren het omdraaien van deze waarheidswaarden, ten nadele van een 'ander, parallel universum'. De natuurkunde zelf werd beïnvloed door het veranderen van de regels van de wiskunde, dus er was overal chaos toen de 'anderen' terug vochten. (En ja, ik heb een doctoraat in zuivere wiskunde)
... en hoe weet je dat P = NP niet waar is in ons universum? Laat het me weten en ik deel de $ 1 miljoen met je.
@DavidRoberts Ik had de vraag moeten formuleren als een roman die zich afspeelt in een universum waar we P = NP kennen :) Re: Egan, ik interpreteerde het verhaal als een draai aan de intensionele definitie. Onze theorie is gebaseerd op een intensieve definitie, wat niet betekent dat het universum het daarmee eens is, en aangezien we niet hebben geprobeerd om de extensionele versie van onze definities te verifiëren, is het fysieke universum het daar misschien niet mee eens.
Misschien allemaal ... Omdat het op dit moment een onopgelost probleem is. :-)
De [MathFiction Homepage] (http://kasmana.people.cofc.edu/MATHFICT/) zou een goed startpunt zijn voor zoiets.
Kun je in * echt * eenvoudige bewoordingen uitleggen wat P = NP betekent en hoe we zouden weten of een boek dat we lezen in dat universum zou zijn?
@Wikis: In een P = NP-universum _finding_ een juiste oplossing voor een grote en goed gedefinieerde hiërarchie van problemen zou slechts zo complex zijn als het _herkennen_ dat een voorgestelde oplossing voor een dergelijk probleem juist is. In ons universum lijkt het bijvoorbeeld veel gemakkelijker om te erkennen dat een kunstwerk geweldig is dan het maken van een geweldig werk. In een universum waar P = NP, zou de vereiste hoeveelheid inspanning hetzelfde zijn of slechts bescheiden groter als we kijken naar de omvang van het op te lossen probleem. Het gemakkelijk kraken van bijna alle vormen van versleuteling is een ander teken van een P = NP-universum.
@DrG: Greg Egan zou waarschijnlijk een roman kunnen schrijven waarin P en NP de hoofdrolspelers zijn. Die kerel laat Kim Stanley Robinson op George Lucas lijken.