Reacties op: Optimale Golomb-liniaal gevonden

Door: HJ

HJ — Mon, 12 Jan 2009 09:20:42 +0000

Toepasselijk: lees deze maand de blog Recursivity van Jeffrey Shallit (hier bij de wismeisjes in de kantlijn gelinkt). Hij laat zien dat ook oude en wijze wiskundigen niet hoeven te begrijpen wat NP nu eigenlijk betekent. "As stated, Dyson's example of the traveling salesman problem is not even in NP, since he states it in the form of finding the shortest tour, as opposed to checking the existence of a tour of length less than a given bound. (If I give you a traveling salesman tour, nobody currently knows how to check in polynomial time that it is the shortest one.)". De prijs voor de Blaaskaak van de Maand is voor Freeman Dyson.

Door: Vincent

Vincent — Sun, 11 Jan 2009 18:02:10 +0000

NP-hard betekent dat ieder NP probleem daarin polynomiale tijd naar vertaald kan worden?

Door: Willem Jan

Willem Jan — Sun, 11 Jan 2009 17:13:22 +0000

Om ook nog even terug te komen op het certificaat: als het vinden van een optimale Golomb-liniaal NP zou zijn, dan zou een certificaat een bewijs (van polynomiale lengte) moeten zijn dat er geen kortere linialen bestaan.

Ik heb eigenlijk geen idee of het redelijk is om te verwachten of dit wel of niet bestaat. Ik weet zo snel geen manier die essentieel sneller is dan alle kleinere aflopen.

Door: Willem Jan

Willem Jan — Sun, 11 Jan 2009 16:59:10 +0000

Het vermoeden is dat het vinden van een optimale Golomb-liniaal "NP-hard" is maar niet NP.

Door: Vincent

Vincent — Sun, 11 Jan 2009 13:09:56 +0000

Ha, dankjulliewel!

Er zit toch iets vreemds in. Voor mijn gevoel is de manier om na te gaan dat een gegeven liniaal optimaal is, toch alle kleinere linialen een voor een uitproberen. Als dat in tijd kan dan moet het vinden van een liniaal van lengte x als die bestaat ook in ongeveer die tijd kunnen zou ik zeggen. Zo heb je wel een erg makkelijk bewijs dat P = NP. Kennelijk is er een snellere manier om optimaliteit na te gaan dan alle kleinere proberen, maar wat is dat? Of zit de clou inderdaad in die certificaten? Maar hoe ziet zo'n certificaat er in dit geval uit?

Door: Willem Jan

Willem Jan — Thu, 08 Jan 2009 23:15:16 +0000

Het is niet zo bij een NP-probleem dat de oplossing zelf in polynomiale tijd te controleren moet zijn. De oplossing "met wat extra informatie" (van polynomiale lengte) moet wel in polynomiale tijd te controleren zijn. Voor bijvoorbeeld de beslissingsvariant van het handelsreizigersprobleem ("Bestaat er een rondreis van maximale lengte M?") is het antwoord "Ja" niet in polynomiale tijd te controleren (tenzij P=NP blijkt), maar wel het antwoord "Ja" samen met het certificaat gegeven door een expliciete rondreis van de juiste lengte. Overigens hoeft het antwoord "Nee" niet snel verifieerbaar te zijn. (Daarvoor is de klasse "co-NP" problemen.) Over het handelsreizigersprobleem: de optimaliseringsvariant is inderdaad "even snel" op te lossen als de beslissingsvariant (via reductie tot een aantal beslissingsvarianten), maar ik geloof niet dat de optimaliseringsvariant NP is. (Vanwege het niet kunnen produceren van een certificaat dat een korter pad niet bestaat, waarschijnlijk?)

Door: HJ

HJ — Thu, 08 Jan 2009 16:04:50 +0000

Voor ik antwoord durfde te geven op de vraag van Ionica heb ik toch mijn Garey&Johnson uit de kast getrokken. Het handelsreizigersprobleem (als [ND22] opgenomen onder routing problems) is prominent aanwezig in het boek. G&J beargumenteren dat hiervoor de beslissings variant ('bestaat er een rondreis van maximale lengte M?') niet makkelijker is dan de optimaliserings versie ('geef de kortste rondreis'). Dat beide varianten van een probleem even complex zijn lijkt vaak het geval, maar is niet automatisch geldig vanwege technisch gedoe met reducties van een probleem naar een ander.

Door: Ionica

Ionica — Wed, 07 Jan 2009 09:19:34 +0000

@Vincent: De oplossing moet in polynomiale tijd te controleren zijn, dit hoeft in de praktijk helemaal niet zo snel te zijn:

is ook een polynoom.

@HJ: Het handelsreizigersprobleem (mijn favoriete NP-probleem) is toch ook een optimaliseringsprobleem? Of bedoel je dat alleen het bijbehorende beslissingsprobleem NP-volledig is? Voor mij is het ook wel weer wat jaren geleden dat ik hier echt goed inzat...

Door: HJ

HJ — Tue, 06 Jan 2009 23:29:49 +0000

Dat lijkt me helemaal geen domme vraag. Je intuitie over NP-complete problemen klopt. De links volgend uit het artikeltje hierboven vond ik een uitgebreide uiteenzetting over Golomb Rulers waarin het vermoeden geuit wordt dat het probleem NP-hard is. Dat betekent dat het probleem niet in de klasse NP hoeft te zitten, en dus de oplossingen niet in polynomiale tijd te controleren hoeven te zijn. Dan is er nog de complicatie (tenminste voor mij is dat altijd lastig te vatten) dat de NP problemen standaard beslissingsproblemen zijn ('bestaat er een lineaal van 25 getallen') terwijl dit me een optimalisatieprobleem lijkt ('geef de kortste lineaal van 25 getallen'). Maar helaas, steeds als ik dat wil nalezen is mijn exemplaar van Garey&Johnson uitgeleend.

Door: Vincent

Vincent — Tue, 06 Jan 2009 14:08:17 +0000

Mag ik nog even een domme vraag over dat NP-volledig zijn stellen? Het idee van een NP-probleem is toch dat het heel moeilijk is om een oplossing te vinden, maar dat het heel makkelijk is om te controleren of een gegeven oplossing inderdaad een oplossing is in plaats van zo maar een rij getallen?

Het verhaal dat de oplossing al in 1984 gevonden was, maar dat het het computers 24 jaar kostte om na te gaan dat dit inderdaad een oplossing is, wijst eerder in de tegenovergestelde richting. Interpreteer ik ergens iets verkeerd?