Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



Categorieën

Archief

Optimale Golomb-liniaal gevonden


In Nieuws, door Ionica

Steven mailde ons het heuglijke nieuws dat er een nieuwe optimale Golomb-liniaal is gevonden. ``Wat voor liniaal?'', hoor ik jullie vragen. Een Golomb-liniaal is een reeks positieve gehele getallen waarbij geen twee getallen uit deze reeks hetzelfde verschil hebben. Een voorbeeldje maakt het volgens mij veel duidelijker dan woorden.


Golomb liniaal
De reeks 0,1,4,6 vormt een Golomb-liniaal: elke twee getallen uit de reeks hebben een ander verschil.

Golomb-linialen kunnen verschillende eigenschappen hebben. Een perfecte liniaal bevat alle verschillen tussen 1 en zijn eigen lengte. Een optimale liniaal is de kortste liniaal met n getallen (waarbij kortste betekent dat het laatste getal uit de reeks zo klein mogelijk is). Het voorbeeld hierboven is zowel optimaal als perfect.

Het zoeken van optimale linialen is niet eenvoudig, sterker nog, er wordt vermoed dat dit een NP-volledig probleem is. Distributed.net maakte zaterdag bekend dat ze een optimale Golomb-liniaal met 25 getallen hebben gevonden. Hier is hij:

0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480.

Het duurde jaren rekenen met duizenden computers om te bewijzen dat deze Golomb-liniaal inderdaad de kortste is voor 25 getallen. De reeks zelf was overigens al in 1984 gevonden [1]. Op naar een liniaal met 26 getallen!

Het zoeken naar grote perfecte Golomb-linialen is trouwens nóg moeilijker. Vooral omdat bewezen is dat ze niet kunnen bestaan voor meer dan vijf getallen.

[1] M. D. Atkinson and A. Hassenklover, "Sets of Integers with Distinct Differences", School of Computer Science, Carlton University, Ottawa Ontario, Canada, Report SCS-TR-63, August 1984.

p.s. Vinden jullie ook niet dat zo'n voetnoot heel wetenschappelijk staat?

18 reacties op “Optimale Golomb-liniaal gevonden”

  1. Pieter:

    Wat goed om te horen... Toevallig deed ik sinds een week of twee mee met het rekenen aan deze linealen.

    Ook een beetje mijn prestatie, op deze manier :-).

  2. Gijsbert:

    Wat betekent precies: Een golomb liniaal kan niet bestaan voor meer dan vijf getallen?

  3. Reijer:

    @Gijsbert: Dat ging over een perfecte Golomb liniaal. Ofwel, voor n>5 bestaat er geen enkele set van n getallen zdd de verschillen van deze getallen precies 1 t/m n zijn, en elk van deze maar een keer.

    Overigens maakt dit in mijn optiek het zoeken naar grote perfect Golomb linialen juist makkelijk (Klaar! Ze zijn er niet), ipv moeilijk ;).

  4. Marco:

    @Reijer: Bij een perfecte Golomb-lineaal gaat het niet om een set van n getallen, maar om een set getallen waarvan het grootste gelijk is aan n. Zie het voorbeeld. Verder helemaal eens met je uitleg.

  5. Proeme:

    hmm... ik begrijp het idee van de perfecte Golomb lineaal niet helemaal. Welke getallen moeten er nou als verschil inzitten? is dat (in het voorbeeld) 1,2,3 en 4?

    @Reijer: het is maar hoe je 'moeilijker' bekijkt. Als ze niet bestaan, is het wel idioot moeilijk om ze te vinden...

  6. Reijer:

    @Marco: Ah ja, dank voor de verbetering :).

    @Proeme: dat was precies waarom ik "in mijn optiek" zei. En om nog even verder te muggenziften; het ging over de moeilijkheid van het zoeken, niet van het vinden ;).

  7. Marco:

    @Proeme: In het voorbeeld is de lengte van de lineaal 6. De verschillen zijn aangegeven met de pijlen en zijn dus 1, 2, 3, 4, 5 en 6. Het is een Golomb-lineaal omdat deze zes getallen allemaal verschillend zijn. Deze Golomb-lineaal is perfect omdat deze zes getallen ook precies alle getallen van 1 t/m 6 zijn. Helpt dit?

  8. Proeme:

    ja, dat helpt. Ik was wat in de war door het begrip lengte.
    De lengte is dus gewoon het verschil tussen het grootste en het kleinste getal (en niet het aantal getallen, zoals ik dacht). En 'kortste' betekent dat het kleinste getal zo laag mogelijk is.

    verwarrend hoor :S maar goed, ksnap hem nu

  9. Vincent:

    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?

  10. HJ:

    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.

  11. Ionica:

    @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...

  12. HJ:

    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.

  13. Willem Jan:

    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?)

  14. Vincent:

    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?

  15. Willem Jan:

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

  16. Willem Jan:

    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.

  17. Vincent:

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

  18. HJ:

    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.

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.