Presná definícia
Čo znamená riešič SAT?
Riešič SAT je program, ktorý rozhoduje splniteľnosť booleovskej formuly, zvyčajne v konjunktívnej normálnej forme. Moderné CDCL solvery používajú propagáciu jednotkových klauzúl, rozhodovanie, analýzu konfliktu, učenie klauzúl a reštarty. Vracia model SAT alebo dôkaz či stav UNSAT.
Skúsenosť a kontext
Ako sa pojem používa v praxi
Plánovanie alebo verifikácia sa zakóduje do SAT a solver nájde priradenie. Wrapper uchová mapu medzi premennými a doménou, časový limit a seed. Model sa po návrate dosadí do pôvodných obmedzení a UNSAT dôkaz sa overí nezávislým checkerom.
Overiteľnosť
Odborné zdroje
Praktické odpovede
Často kladené otázky
Ako funguje riešič SAT?
CDCL vyberie literál, propaguje dôsledky a po konflikte naučí klauzulu, ktorá zabráni opakovaniu rovnakej slepej vetvy.
Kedy má riešič SAT praktický význam?
Plánovanie alebo verifikácia sa zakóduje do SAT a solver nájde priradenie.
S čím si pojem nezamieňať?
Constraint solver môže pracovať s celočíselnými a globálnymi obmedzeniami; SAT solver rieši booleovské klauzuly priamo alebo po kódovaní.
Ako sa výsledok kontroluje?
Kontroluje sa model, certifikát UNSAT, výkon benchmarkov, deterministickosť konfigurácie a správnosť enkódovania.
Na čo si dať pozor?
Timeout nie je UNSAT a neefektívne kódovanie môže z jednoduchého doménového problému vytvoriť ťažkú formulu.