Den löpande prestandan hos moderna SAT-lösare på slumpmässiga k-CNF-formler är djupt kopplad till "fasövergång" fenomenet sett empiriskt i tillfredsställelsen av slumpmässiga k-CNF-formler. Senaste universella hashing-baserade metoder för provtagning och beräkning är avgörande beroende av körtiden prestanda SAT lösare på formler som uttrycks som en kombination av både k-CNF och XOR begränsningar (känd som k-CNF-XOR formler), men beteendet hos slumpmässiga k-CNF-XOR formler är outforskad i tidigare arbete. I detta dokument presenterar vi den första studien av tillfredsställandet av slumpmässiga k-CNF-XOR-formler. Vi visar empiriska belägg för en överraskande fasövergång som följer en linjär avvägning mellan k-CNF och XOR-begränsningar. Dessutom bevisar vi att det finns en fasövergång för k-CNF-XOR-formler för k = 2 och (när antalet k-CNF-begränsningar är litet) för k > 2.
I REF studerades först tillfredsställandetröskeln för kombination av slumpmässiga XOR-formler för k-CNF och slumpmässiga XOR-formler med variabel bredd.
Combining the $k$-CNF and XOR Phase-Transitions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}