pith. sign in
module module high

IndisputableMonolith.Complexity.SAT.PC

show as:
view Lean formalization →

The PC module unifies CNF clauses and XOR parity checks into a single constraint representation for SAT instances. Researchers modeling hybrid constraint problems or proving completeness in mixed logical systems would cite these definitions. The module supplies inductive types, mention predicates, and witness structures with no theorems or proofs.

claimA constraint over $n$ variables is either a CNF clause on literals or an XOR check requiring the parity of a variable subset to equal a specified bit in $0,1$.

background

The module sits inside the SAT complexity layer and imports the CNF module, where variable indices are Fin n for a given problem size, together with the XOR module, where an XOR constraint over n variables requires that the parity of a variable subset equals a given parity. It introduces the unified constraint form, predicates that detect variable mentions in literals or clauses, satisfaction checks, and auxiliary structures for input sets and peeling witnesses that track how constraints determine variables.

proof idea

This is a definition module, no proofs.

why it matters in Recognition Science

These definitions are imported by the Completeness module to build a fully-determined backpropagation state from a total assignment. The module supplies the uniform constraint representation required for completeness arguments that handle both clause and parity constraints together.

scope and limits

used by (1)

From the project-wide theorem graph. These declarations reference this one in their body.

depends on (2)

Lean names referenced from this declaration's body.

declarations in this module (23)