FPRD LabShare an approach

← Claims

Theorem · exact separating example

CRD-SAT-10b

A smallest second-order branching separation

Exact statement

For D=(x∨¬z∨¬p)∧(y∨¬z∨p)D=(x\vee\neg z\vee\neg p)\wedge(y\vee\neg z\vee p) and D+=D∧(x∨y∨¬z)D^+=D\wedge(x\vee y\vee\neg z), the databases are semantically equivalent and have the same singleton unit-propagation signature, yet fixed false-first DPLL in the order x<y<z<px<y<z<p uses three decisions on DD and two on D+D^+, with no conflicts.

StatusProved for the displayed databases and fixed DPLL policy
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The example separates one-literal observations from behavior that appears only when two decisions jointly activate a retained resolvent.

Definitions

  • The added clause x∨y∨¬zx\vee y\vee\neg z is the pure resolvent of the two source clauses on pp.
  • DPLL exhausts unit propagation, stops when every stored clause is satisfied, branches in the displayed order, and tries false first.

Hypotheses and scope

  • Clause satisfaction is checked after each unit-propagation closure.
  • The branching policy is fixed independently of the clause database.

Proof or evidence

Resolution proves semantic equivalence. By CRD-SAT-10a, both strict-3CNFs have trivial singleton closure. Under x=y=0x=y=0, the base reduces to (¬z∨¬p)∧(¬z∨p)(\neg z\vee\neg p)\wedge(\neg z\vee p) and stalls, whereas the resolvent becomes the unit ¬z\neg z. The fixed traces therefore have costs (3,0)(3,0) and (2,0)(2,0).

Second-order separation proof →

Verification notes

The semantic, propagation, and fixed-policy conclusions were checked separately. The packet's exhaustive census is corroboration, not the proof.

Limitations

  • Choosing zz first and trying false erases the decision gap.
  • The pair differs at seed size two and has no conflict on the exhibited trace.
  • This is not a SAT-hardness, proof-size, or average-heuristic result.

Open work

Use the parameterized CRD-SAT-11 family for conclusions across clause widths.