Skip to main content
deleted 5 characters in body
Source Link

A clause in 3-CNF can be converted to k-CNF by adding extra padding:

(l1 V l2 V l3) can be converted to (l1 V l2 V l3 V y) ∧ (l1 V l2 V l3 V y')

Keep adding this extra padding until each clause contains k literals.

Same way, a k-CNF clause can be broken until each clause contains 3 literals.

(l1 V l2 V l3 V l4) can be broken into (l1 V l2 V l3 V y) ∧ (l1 V l2l3 V l3l4 V y') by resolution.

A clause in 3-CNF can be converted to k-CNF by adding extra padding:

(l1 V l2 V l3) can be converted to (l1 V l2 V l3 V y) ∧ (l1 V l2 V l3 V y')

Keep adding this extra padding until each clause contains k literals.

Same way, a k-CNF clause can be broken until each clause contains 3 literals.

(l1 V l2 V l3) can be broken into (l1 V l2 V l3 V y) ∧ (l1 V l2 V l3 V y') by resolution.

A clause in 3-CNF can be converted to k-CNF by adding extra padding:

(l1 V l2 V l3) can be converted to (l1 V l2 V l3 V y) ∧ (l1 V l2 V l3 V y')

Keep adding this extra padding until each clause contains k literals.

Same way, a k-CNF clause can be broken until each clause contains 3 literals.

(l1 V l2 V l3 V l4) can be broken into (l1 V l2 V y) ∧ (l3 V l4 V y') by resolution.

Source Link

A clause in 3-CNF can be converted to k-CNF by adding extra padding:

(l1 V l2 V l3) can be converted to (l1 V l2 V l3 V y) ∧ (l1 V l2 V l3 V y')

Keep adding this extra padding until each clause contains k literals.

Same way, a k-CNF clause can be broken until each clause contains 3 literals.

(l1 V l2 V l3) can be broken into (l1 V l2 V l3 V y) ∧ (l1 V l2 V l3 V y') by resolution.