Chapter 12: Complexity J;J, 371
12.7 Find whether (P /\ Q /\ R) /\ -, Q is satisfiable.
12.8 Is f(x, y, z, w) = (x v y v z) /\ (x V y v z) satisfiable?
12.9 The set of all languages whose complements are in NP is called
CO-NP. Prove that NP = CO-NP if and only if there is some
NP-complete problem whose complement is in NP.
12.10 Prove that a boolean expression E is a tautology if and only if -, E is
unsatisfiable (refer to Chapter 1 for the definition of tautology).
12.7 Find whether (P /\ Q /\ R) /\ -, Q is satisfiable.
12.8 Is f(x, y, z, w) = (x v y v z) /\ (x V y v z) satisfiable?
12.9 The set of all languages whose complements are in NP is called
CO-NP. Prove that NP = CO-NP if and only if there is some
NP-complete problem whose complement is in NP.
12.10 Prove that a boolean expression E is a tautology if and only if -, E is
unsatisfiable (refer to Chapter 1 for the definition of tautology).