Author |
Topic: NEW PROBLEM: 1-IN-3SAT (Read 4943 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
NEW PROBLEM: 1-IN-3SAT
« on: Oct 2nd, 2002, 7:53am » |
 Quote  Modify
|
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.
|
| « Last Edit: Oct 2nd, 2002, 7:55am by Pietro K.C. » |
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: NEW PROBLEM: 1-IN-3SAT
« Reply #1 on: Oct 11th, 2002, 5:52pm » |
Quote Modify
|
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.
|
| « Last Edit: Oct 11th, 2002, 5:54pm by Jonathan_the_Red » |
IP Logged |
My arcade cabinet
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PROBLEM: 1-IN-3SAT
« Reply #2 on: Oct 11th, 2002, 6:27pm » |
Quote Modify
|
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 Ci = x + y + z to the following:
(x + aix + bix)*(y + aiy + biy)*(z + aiz + biz)*(aix + aiy + aiz)*(bix + biy + biz).
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.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print