Friday, September 10, 2010

Problem reduction and SAT questions...

Qn 1.

Give a solution to the following SAT problem:

Variables: P , Q, R

Clauses:  P V Q
                 ~P V R
                 ~Q V R
                   ~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? 


                

8 comments:

  1. 1. I'm a little unclear on problem 1. Are we to find the combination of true false where all of these clauses are satisfied at the same time, or just one at a time i.e. P v Q ; ~P v R? Please clairify

    2. I would imagine that 1 SAT problems would be pretty easy... given one variable would just have to match the other and you only have 2 choices of false and true.

    3. 2 SAT problems have been proven to be solvable in polynomial time in given instances. Though harder than 1 SAT problems, they are not NP-complete class problems.

    4. I'm not sure how

    ReplyDelete
  2. 1.
    ~R means R must be false.
    ~Q V R means ~Q must be true, thus Q is false.
    ~P V R means ~P must be true, thus P is false.
    P V Q will therefor never evaluate to true...

    Therefor, no solution exists.

    2. Aren't k-SAT problems only NP-complete if k>2?

    3. This is a P-Complete problem.

    4. Yeah, Im not familiar with such tasks...

    ReplyDelete
  3. Qn 1. I don't know how to solve these. I have never learned what the ~ and V means. I know we went over it in class for a sec, but I do not remember.

    Qn 2. These are P-Complete problems

    Qn 3. These are NL-Complete problems

    Qn 4. 6,4,7,8,9,10,11

    is 6<4? True/False or 1/0
    done.

    ReplyDelete
  4. 1. Based off of what i know about this type of logic, i made a truth table. Im not entirely sure, but for any solution, all of the conditions have to come up with a 1 as the result. so in the truth table it would be a line of 1's. Of the 8 possible orginization of 1's and 0's for the variables, none of the set up's resulted in a line of ones. so that makes me believe that there is no solution.

    2. I would think that 1-SAT problems would be much "easier" and thusly, be completeable in poly time.

    3. I dont really understand why 3-sat is np-complete, because i dont see where the 2^n comes in anywhere.. but yeah, i'd have to go with what i said for #2, in that it should be possible in poly time.

    4. i like how Michael Wenz did that. so i'll quote him for my answer. "is 6<4? True/False" - Michael Wenz.

    ReplyDelete
  5. 1. If the (~) means not ... I think its doesn’t have a solution.

    2. 1-SAT problems are easy because they all clauses have at most 1 literal, this are P-complete.

    3. 2 SAT will also be P-SAT

    4. I truly didn’t understand this question.

    ReplyDelete
  6. 1. It doesnt have a solution... it would seem to be pretty easy but i guess you cant do it

    2. 1SAT problems should be very easy

    3. 2SAT could be done in polynomial time

    4. no idea

    ReplyDelete
  7. 1. Has no solution because ~r is false therefore the rest is false

    2. 1-sat should be much easier than 3 sat and should take significantly less time to solve

    3. 2-sat can be done

    4. Please explain.

    ReplyDelete
  8. 1. This problem doesn't have a solution. There's only a bunch of false statements(?). Well....they turn out false at least.

    2. 1SAT problems should be easier...because there's a lot less to deal with.

    3. same thing applies. It's harder than 1SAT...but easier than 3SAT...and it's possible to do in polynomial time, according to the wonders page on Wikipedia.

    4. As for this problem....I would have absolutely no idea what to do. Nor do I have an idea of what's going on.

    ReplyDelete

Note: Only a member of this blog may post a comment.