 Home

Codex Wiki

Computer science

Theoretical computer science

Computational complexity theory

Polynomial-time reduction

Polynomial-time many-one reduction

NP-hardness

NP-completeness

Boolean satisfiability problem

Boolean formula

Conjunctive normal form

{title2=$\bigwedge_i(\ell_{i,1}\lor\ell_{i,2})$}

A <Boolean formula> in <conjunctive normal form> with at most two <Boolean literals> per <Boolean clause>. Shorter <Boolean clauses> are allowed. The <Boolean satisfiability problem> restricted to these <Boolean formulas> is <2-SAT>.

2-CNF formula

Past exam of the computer science course of the University of Oxford / 2015 / Logic and proof / 1 / c / Solution

2-CNF formula ( $⋀_{i} (ℓ_{i, 1} \lor ℓ_{i, 2})$ )

 Ancestors (11)

 Incoming links (1)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

2-CNF formula (⋀i​(ℓi,1​∨ℓi,2​))

 Ancestors (11)

 Incoming links (1)

 Discussion (0)  Subscribe (1) New discussion

 Articles by others on the same topic (0)

2-CNF formula ( $⋀_{i} (ℓ_{i, 1} \lor ℓ_{i, 2})$ )

 Discussion (0) New discussion