wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> NEW PROBLEM: 1-IN-3SAT
        
(Message started by: Pietro K.C. on Oct 2^nd, 2002, 7:53am)

Title: NEW PROBLEM: 1-IN-3SAT
Post by Pietro K.C. on Oct 2^nd, 2002, 7:53am

Just when you thought you'd had enough of that pesky SAT problem... not so.

Let 1-in-3SAT be the defined identically as 3SAT (which I assume you, checking out the CS forum, know or are able to Google), with the catch that, in each clause, EXACTLY ONE of the literals must be assigned the value TRUE. For instance,

F = (x + y + z)(x' + y' + z')

obviously has an affirmative answer according to 3SAT (just make x = TRUE, y = z = FALSE). However, 1-in-3SAT would return NEGATIVE, since there is no possible attribution that would make exactly one literal in (x + y + z) be true AND exactly one literal in (x' + y' + z') be true.

Prove that 1-in-3SAT is NP-complete.

Title: Re: NEW PROBLEM: 1-IN-3SAT
Post by Jonathan_the_Red on Oct 11^th, 2002, 5:52pm

This is the first one of these I've attempted. I kinda liked it... I think this one is suitable for beginners :)

Spoiler...

Consider a clause in the 3-CNF equation, (X + Y + Z). Use a three-digit binary number to label all the possible values of X, Y, and Z, of which there are 8. This clause asserts that (000) is NOT one of the possible values, which is fine, but it doesn't take us far enough. Transmogrify each triplet (what's the correct term, anyway?) as follows:

(X+Y+Z) * _{(not 000)}
(X'+Y'+Z) * _{(not 110)}
(X'+Y+Z') * _{(not 101)}
(X+Y'+Z') * _{(not 011)}
(X'+Y'+Z') _{(not 111)}

This will resolve to true if the pattern is (100), (010), (001), which is what we want. Hence the problem is equivalent to 3-SAT, which of course is NP-complete.

Title: Re: NEW PROBLEM: 1-IN-3SAT
Post by Pietro K.C. on Oct 11^th, 2002, 6:27pm

Well, that's a pretty cool (and straightforward) solution! I like it. Mine is different, and it seems I had a little trouble going straight to the point, as you did. Here it is:

convert a clause C_i = x + y + z to the following:

(x + a_ix + b_ix)*(y + a_iy + b_iy)*(z + a_iz + b_iz)*(a_ix + a_iy + a_iz)*(b_ix + b_iy + b_iz).

It's pretty clear why it works.

Yeah, it's really for beginners - it was on the first problem set of my analysis of algorithms II class this semester. But I thought it was a nice reduction! :) Now go give the other SAT problem a shot, and also the spanning tree one. They were also taken from that problem set.