Il risolutore SAT ortologico supera Kissat su benchmark difficili

Un algoritmo innovativo per l'implicazione ortologica elimina la necessità di costose preelaborazioni, mantenendo una complessità nel caso peggiore di O(n^2(1+|A|)). I ricercatori presentano benchmark SAT sintetici derivati dalla tautologia φ ↔ NF_OL(φ), dove la codifica di Tseitin produce casi insoddisfacibili che sfidano i principali risolutori come Kissat ma consentono dimostrazioni ortologiche concise. Testato sui circuiti aritmetici EPFL, questo algoritmo risolve efficacemente questi casi, mentre Kissat non riesce a completarne un numero considerevole. Implementare la normalizzazione ortologica come fase di preelaborazione può migliorare l'efficienza della risoluzione SAT per alcuni problemi difficili.