Concept icon
Concept

Conditional contraction bound for a fixed-density CNF

Assuming the stated contraction theorem, set s=n+m, P0=n+1 and ell=1 for the bipartite clause network. For fixed width k, its local tables have constant size, wire count is O_k(s), and bounded degree eventually satisfies the theorem threshold. Handle the finitely many failing sizes by direct counting. The residue readout then gives time s^{O_k(1)} 2^{O_k(s/sqrt(log s))} and polynomial space. If m<=Dn for fixed D, then n<=s<=(1+D)n, giving exponent O_(k,D)(n/sqrt(log n)). The speed conclusion depends on the separate contraction theorem; the encoding correctness does not.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math