Semantic Lifting, Closure Dimension, and Metastable Barriers in Boolean Satisfiability

Read full text
Authors: William Bailey
Cited by: 0

Abstract

This work develops a structural framework for analyzing Boolean satisfiability (SAT) through semantic lifting, closure dimension, metastable barrier height, and charged syllogisms. By examining polynomial-time fragments such as XOR-SAT and 2-SAT, we show that tractability arises when a richer semantic embedding exposes invariants that collapse under a finite, local tightening system to a canonical normal form. General CNF-SAT resists such collapse because known embeddings induce unbounded closure growth, producing metastable barrier instances. The paper does not claim a resolution of the P vs. NP problem. Instead, it provides a unifying conceptual explanation for why certain satisfiability fragments are tractable, why known approaches fail in general, and what properties a hypothetical “winning” embedding would need to possess.

Fields of Study & Subjects

Formal Methods in Verification Advanced Graph Theory Research Complexity and Algorithms in Graphs

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
2 January 2026
Language
EN
Document type
Preprint