Homework 5: A note on the last problem

November 23rd, 2008

You’ll notice that the new clauses I construct have only 2 variables, and are thus not correct instances of planar 3SAT. It’s trivial to fix this problem, but make sure you do so.

This entry was posted on Sunday, November 23rd, 2008 at 10:32 pm and is filed under news.

5 Responses to “Homework 5: A note on the last problem”

  1. Brad Grimm Says:
    November 24th, 2008 at 9:48 am

    Is x_1 or x_2 or x_1 a valid instance of 3SAT? Or does it need to have 3 distinct variables.

  2. Brad Grimm Says:
    November 24th, 2008 at 9:51 am

    If that isn’t a valid instance of 3SAT are we allowed to force a 1 or 0 variable? So that our 3SAT will be: x_1 or x_2 or 1.

  3. admin Says:
    November 24th, 2008 at 11:23 am

    you can’t repeat. but something along those lines will give you what you want. maybe you need one more clause, and a new variable

  4. Mike Clark Says:
    November 24th, 2008 at 4:40 pm

    Does the fact that we have to fix this problem change the statement in the homework that we need at least 4 more variables, or will that number be greater since we have to make the change?

  5. admin Says:
    November 24th, 2008 at 5:50 pm

    I meant that you’ll need at least 4 more inside the gadget. the extras you need to “fix” 2-variable clauses are extra (but are modular: the same trick works everywhere).

Leave a Reply