Golomblinjal
 |
Den här artikeln behöver källhänvisningar för att kunna verifieras. (2020-08) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. |
En Golomblinjal är en matematisk term för en uppsättning heltalspositioner längs en tänkt linjal där inga av avstånden mellan positionerna är lika. Antalet positioner benämns som Golomblinjalens grad och det längsta avståndet mellan två av dess positioner för dess längd.
Den kortast möjliga linjalen för varje grad kallas den optimala Golomblinjalen. Optimala Golomblinjaler är användbara vid konstruktion av bland annat radioteleskop. En linjal som klarar att mäta samtliga avstånd upp till dess längd kallas perfekt. Det är bevisat att det inte existerar några perfekta linjaler med fem eller fler positioner.
Optimala Golomblinjaler måste hittas numeriskt och det görs bland annat ett arbete av frivilligorganisationen Distributed.net. I nuläget är komplexiteten för att finna en golomblinjal av längd n okänd men problemet tros vara NP-svårt.