Revisiting Incremental Linearization for Nonlinear Integer Arithmetic

Stel je voor dat je een detective bent die een mysterie probeert op te lossen, maar de aanwijzingen die je krijgt, zijn geschreven in een taal waarvan de betekenis verandert afhankelijk van hoe je ernaar kijkt. Dit is de wereld van Satisfiability Modulo Theories (SMT), een tak van de informatica waar software probeert uit te zoeken of een reeks logische regels ooit tegelijkertijd waar kan zijn. Denk aan het als een superintelligente puzzeloplosser die controleert of een programma crasht, of een geheime code gekraakt kan worden, of of het pad van een robot veilig is.

Meestal zijn deze puzzels eenvoudig omdat ze alleen bestaan uit rechte lijnen en eenvoudige optellingen (zoals $x + y = 5$). Computers zijn hier geweldig in. Maar het leven wordt rommelig wanneer je niet-lineaire rekenkunde introduceert—regels waarbij dingen met elkaar vermenigvuldigd worden of tot machten worden verheven (zoals $x \times y$ of $x^3$). Plotseling buigen en draaien de regels en wordt de wiskunde ongelooflijk moeilijk. Sterker nog, voor gehele getallen is het wiskundig onmogelijk om een perfecte, 100% volledige methode te creëren die al deze puzzels oplost. Daarom bouwen computerwetenschappers "goed genoeg" detectives die slimme afkortingen gebruiken om snel antwoorden te vinden, zelfs als ze niet kunnen garanderen dat ze elk onmogelijk geval oplossen.

De paper die je nu gaat lezen, introduceert een nieuwe detective, genaamd qfn2l, die beter is in het oplossen van deze lastige, kromme puzzels dan de detectives die we hiervoor hadden. De auteurs, onderzoekers van de Tsjechische Technische Universiteit in Praag, realiseerden zich dat de oude afkortingen moeite hadden met een specifiek type moeilijke puzzel: die met machten (zoals $x^3$) en gemengde producten (zo zoals $x^2y$). Ze besloten de gereedschapskist van de detective te upgraden met een nieuwe set regels die fungeren als een nauwer net, waardoor de slechte gissingen die voorheen ontsnapten, nu wel worden gevangen.

De Oude Manier: Gissen met Ongeïnterpreteerde Functies

Om de upgrade te begrijpen, laten we kijken naar hoe de vorige detectives werkten. Stel je een mysterieuze doos voor met het label $f(x, y)$. Je weet niet wat erin zit, maar je weet dat als je dezelfde getallen erin stopt, je hetzelfde getal eruit krijgt. De oude methode behandelde elke vermenigvuldiging, zoals $x \times y$, als deze mysterieuze doos. De computer zou een waarde voor de doos raden, controleren of dit logisch was, en als dat niet zo was, zou hij een regel toevoegen om de gok te corrigeren.

Dit werkte redelijk voor eenvoudige gevallen, maar het was alsoals proberen het gewicht van een watermeloen te raden door alleen te weten dat hij "zwaar" is. Het was te vaag. Wanneer de puzzel complexe machten bevatte, zoals $x^3$, waren de oude regels te losjes. De detective zou een waarde raden, de computer zou zeggen: "Nee, dat klopt niet," en vervolgens een zeer zwakke regel toevoegen om de gok te corrigeren. De detective zou moeten raden, falen en weer opnieuw raden, vaak honderden keren, waardoor hij vaak zonder tijd kwam te zitten voordat hij het antwoord vond.

De Nieuwe Truc: Het Net Aanhalen met Secanten

De auteurs van deze paper besloten te stoppen met het behandelen van deze machten als mysterieuze dozen en ze in plaats daarvan te behandelen als nieuwe constanten—gewoon simpele getallen die het resultaat van de macht vertegenwoordigen. Maar de echte magie zit in de nieuwe regels die ze toevoegden om deze getallen te controleren.

Ze ontdekten dat voor elk geheel getal, zeg $v$, de functie $x^k$ (zoals $x^3$) op een zeer voorspelbare manier gedraagt tussen $v$ en $v+1$. Ze creëerden een nieuwe set regels gebaseerd op secantlijnen. Stel je een curve op een grafiek voor. Een secantlijn is een rechte lijn die twee punten op die curve verbindt. De auteurs realiseerden zich dat als je een rechte lijn trekt tussen het punt $(v, v^k)$ en het volgende gehele punt, die lijn een zeer strakke "omheining" rond de curve creëert.

Hier is de analogie:

• De Oude Manier: De detective tekende een enorme, losse cirkel rond de mogelijke antwoorden. Het was makkelijk te tekenen, maar het liet veel foute gissingen toe.
• De Nieuwe Manier: De detective tekent een reeks strakke, rechte hekken (secantlijnen) die de curve van het antwoord heel dicht volgen. Als een gok buiten deze strakke hekken valt, weet de detective onmiddellijk dat het fout is en voegt hij een regel toe om de gok weer binnen de lijnen te duwen.

Omdat deze hekken zo strak zijn, hoeft de detective niet veel minder vaak te raden. Hij convergeert veel sneller naar het juiste antwoord, vooral bij puzzels die betrokken zijn bij kubussen en gemengde producten.

De "Som van Drie Cubes" Uitdaging

Om te bewijzen dat hun nieuwe detective werkte, testten de auteurs hun solver op een beroemde klasse van puzzels genaamd de "som van drie kubussen". Dit zijn problemen die vragen: "Kun je drie gehele getallen vinden die, wanneer je ze tot de derde macht verheft en bij elkaar optelt, een specifiek getal opleveren?"

Bijvoorbeeld, de puzzel zou kunnen zijn: $x^3 + y^3 + z^3 = 79$.

Dit is een nachtmerrie voor standaard solvers. De getallen kunnen enorm zijn en de relaties zijn complex. De auteurs testten hun nieuwe solver, qfn2l, tegen de beste bestaande solvers (zoals Z3, cvc5 en MathSAT).

• De andere solvers probeerden de $x^3 + y^3 + z^3 = 79$ puzzel op te lossen, maar gaven het op na 3 minuten (ze "timed out").
• De nieuwe solver, qfn2l, vond het antwoord—$x = -19, y = 35, z = -33$—in slechts 20 seconden.

De Resultaten: Een Competitieve Nieuwe Uitdager

De onderzoekers hebben hun solver getest op een enorme collectie van 25.444 puzzels uit een standaardbibliotheek genaamd SMT-LIB. Dit is wat ze vonden:

1. Algemene Prestaties: De nieuwe solver is competitief met de beste tools van dit moment. Hij loste in totaal ongeveer 14.000 puzzels op, wat dicht bij de topperformers ligt, hoewel hij niet op elke enkele type puzzel de allerbeste (zoals Z3) versloeg.
2. Het Optimale Gebied: De nieuwe solver blinkt absoluut uit in de puzzels die gedomineerd worden door machten en gemengde producten. Op de "MathProblems" familie (die de som van kubussen bevat), loste hij ongeveer 53% van de instanties op (585 tot 587 van de 1.100). De andere solvers hadden veel meer moeite met deze specifieke soorten problemen.
3. De Afweging: De auteurs testten een versie van hun solver die probeerde extra voorzichtig te zijn bij het controleren of verschillende delen van de puzzel consistent zijn (genaamd "congruence axioms"). Ze ontdekten dat deze extra controle de solver juist vertraagde op algemene puzzels, waarbij ongeveer 1.600 instanties minder werden opgelost. Dit suggereert dat voor de meeste problemen de strakke hekken (secant bounds) voldoende zijn en dat je niet de extra zware berekeningen nodig hebt om elke enkele consistentieregel te controleren.

Waarom Dit Belangrijk Is

De paper beweert niet dat ze het onoplosbare hebben opgelost. Ze geven toe dat, omdat het probleem wiskundig onbeslisbaar is, geen enkele computer elk geval kan oplossen. Echter, ze hebben aangetoond dat door de manier waarop we deze kromme, niet-lineaire regels benaderen te veranderen—specifiek door gebruik te maken van deze strakke, op secanten gebaseerde hekken—we de "goed genoeg" detectives veel slimmer kunnen maken.

Ze hebben een tool gebouwd die open-source is en bovenop een bestaande engine (Z3) draait, waarmee ze bewijzen dat een slimmere strategie een brute-force aanpak kan verslaan bij de moeilijkste soorten integer-puzzels. Voor iedereen die probeert te verifiëren of een stuk software niet zal crashen of of een cryptografisch protocol veilig is, biedt deze nieuwe methode een snellere, betrouwbaardere manier om de wiskunde achter de schermen te controleren.

Kortom, de auteurs namen een rommelig, krom probleem en trokken er strakkere lijnen omheen, waardoor computers de waarheid veel sneller kunnen vinden dan voorheen.