Abstrakt. I detta dokument föreslår vi en strategi för att bygga partitioner av hårda varianter av Booleska tillfredsställande problem (SAT). Sådana partitioner kan användas för att lösa motsvarande SAT-fall parallellt. För samma SAT instans kan man konstruera olika partitioner, var och en av dem är en uppsättning förenklade versioner av den ursprungliga SAT instansen. Effektiviteten av en godtycklig partitionering bestäms av den totala tiden för att lösa alla SAT-fall från den. Vi föreslår tillvägagångssättet, baserat på Monte Carlo metoden, för att uppskatta tiden för bearbetning av en godtycklig partitionering. Med varje partitionering associerar vi en punkt i det speciella finita sökutrymmet. Uppskattningen av den specifika partitionens effektivitet är värdet av prediktiv funktion i motsvarande punkt i detta utrymme. Problemet med att söka efter en effektiv partitionering kan formuleras som ett problem för optimering av den prediktiva funktionen. Vi använder metaheuristiska algoritmer (simulerad glödgning och tabu sökning) för att flytta från punkt till punkt i sökområdet. I våra beräkningsförsök hittade vi partitioner för SAT-fall kodning problem med inversion av vissa kryptografiska funktioner. Flera av dessa SAT-fall med realistisk förutsedd lösningstid löstes framgångsrikt på ett datorkluster och i det frivilliga datorprojektet SAT@home. Lösningstiden stämmer väl överens med de uppskattningar som gjorts med den föreslagna metoden.
I REF beskrevs metoden för automatisk sökning efter SAT-partitioner och dess tillämpning för att hitta nya partitioner för SAT-instanser som kodar för kryptoanalys av A5/1 ang Bivium-generatorer.
Using Monte Carlo method for searching partitionings of hard variants of Boolean satisfiability problem
{'venue': 'LNCS 9251 (2015) 222-230', 'journal': None, 'mag_field_of_study': ['Computer Science']}