Scholarlink

This paper studies Locally Maximal Satisfying Truth Assignments (LMSTAs) of satisfiable random k-SAT formulas via Kolmogorov complexity. For Kolmogorov-random instances, we show that the fraction of zeros in any LMSTA lies in a contiguous sub-interval of (0, 1) whose bounds depend on the clause-to-variable ratio r. We further derive a mixed-width version that applies to heterogeneous CNFs. As case studies, we analyse the standard SAT encodings of 200-round Trivium and the public 30-round Bivium benchmark and prove that no LMSTAs exist for either, ruling out single-bit “local traps”. This work links information-theoretic randomness to local maximality providing a heuristic, compression-based test for real-world SAT reductions in cryptography.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Kolmogorov Complexity Based Analysis of the Zeros Distribution in Locally Maximal Satisfying Truth Assignments of Random K-SAT Formulas

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • V. Liagkou,
  • P. E. Nastou,
  • P. Spirakis,
  • Y. C. Stamatiou

摘要

This paper studies Locally Maximal Satisfying Truth Assignments (LMSTAs) of satisfiable random k-SAT formulas via Kolmogorov complexity. For Kolmogorov-random instances, we show that the fraction of zeros in any LMSTA lies in a contiguous sub-interval of (0, 1) whose bounds depend on the clause-to-variable ratio r. We further derive a mixed-width version that applies to heterogeneous CNFs. As case studies, we analyse the standard SAT encodings of 200-round Trivium and the public 30-round Bivium benchmark and prove that no LMSTAs exist for either, ruling out single-bit “local traps”. This work links information-theoretic randomness to local maximality providing a heuristic, compression-based test for real-world SAT reductions in cryptography.