Notes - Logic and Proof MT24, XOR-Clauses

Created: October 14, 2024
Updated: October 19, 2024

What’s the idea behind showing that the satisfiability problem for conjunctions of XOR-clauses can be solved in polynomial time?

Reduce to a system of equations over $\mathbb Z _ 2$ and solve via Gaussian elimination.

[[Course - Logic and Proof MT24]]^U

(outgoing)
[[Notes - Logic and Proof MT24, 2-CNF formulas]]^U

(sim: 0.539)
[[Notes - Logic and Proof MT24, 3-CNF formulas]]^U

(sim: 0.526)
[[Notes - ADS HT24, NP-hardness and NP-completeness]]^U

(sim: 0.514)
[[Notes - Logic and Proof MT24, Boolean circuits]]^U

(sim: 0.503)
[[Notes - Logic and Proof MT24, Resolution]]^U

(sim: 0.501)