Give a solution to the following SAT problem:
Variables: P , Q, R
Clauses: P V Q
~P V R
~Q V R
Qn 2. We saw that 3-SAT, which is the special case of boolean satisfiability problem where all clauses are of length 3, is NP-complete (i.e., as hard as any NP-complete problem). How about 1-SAT? (i.e., SAT problem where all clauses are of length 1)
Qn 3. Continuing Qn 2, how about 2-SAT (i.e., all clauses are of length 2)
Qn 4. We saw that boolean satisfiability is NP-Complete in that every other NP-problem can be reduced to it in polynomial time. Does this hold also for Sorting? Can you think of a way a 2 number sorting problem can be converted into a boolean satisfiability one?