Logic and Proof MT24, XOR-Clauses

Created: October 14, 2024 | Updated: October 19, 2024 | Read markdown | About these notes | View in context | Study these flashcards |

Course - Logic and Proof MT24^U

Flashcards

@Describe 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, All the algorithms^U

(incoming)
Notes - Logic and Proof MT24, 2-CNF formulas^U

(sim: 0.563)
Notes - Logic and Proof MT24, Basic definitions for propositional logic^U

(sim: 0.534)
Notes - Logic and Proof MT24, Decidability results for first-order logic^U

(sim: 0.53)