wu :: forums « wu :: forums - 3SAT and P=NP » Welcome, Guest. Please Login or Register. Apr 20th, 2024, 1:56am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: ThudnBlunder, william wu, SMQ, Icarus, Grimbal, Eigenray, towr)    3SAT and P=NP « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: 3SAT and P=NP  (Read 1665 times) Dudidu Full Member     Posts: 227 3SAT and P=NP   « on: Nov 6th, 2003, 9:55am » Quote Modify Assuming P=NP (), suggest a deterministic polynomial time algorithm that finds a satisfying assignment for a given 3SAT. « Last Edit: Nov 6th, 2003, 10:00am by Dudidu » IP Logged william wu wu::riddles Administrator     Gender: Posts: 1291 Re: 3SAT and P=NP   « Reply #1 on: Nov 6th, 2003, 12:13pm » Quote Modify I believe this is already on the site, and in my understanding, unresolved:   http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1031609156 « Last Edit: Nov 6th, 2003, 12:20pm by william wu » IP Logged [ wu ] : http://wuriddles.com / http://forums.wuriddles.com Dudidu Full Member     Posts: 227 Re: 3SAT and P=NP   « Reply #2 on: Nov 8th, 2003, 12:01pm » Quote Modify on Nov 6th, 2003, 12:13pm, william wu wrote: I believe this is already on the site, and in my understanding, unresolved... William, It's about time that someone will solve it ...   (or unfortunatly I will be obligated to do it ) IP Logged Rezyk Junior Member     Gender: Posts: 85 Re: 3SAT and P=NP   « Reply #3 on: Nov 8th, 2003, 1:41pm » Quote Modify Hmm...what does our algorithm need to do if the given 3SAT has no solution?  Is it okay to never return in that case?   The problem in the other thread asks for an algorithm that "solves" SAT, which generally means it has to halt in polytime, but that's not quite as explicit here. « Last Edit: Nov 8th, 2003, 3:38pm by Rezyk » IP Logged william wu wu::riddles Administrator     Gender: Posts: 1291 Re: 3SAT and P=NP   « Reply #4 on: Nov 8th, 2003, 3:56pm » Quote Modify Right, this is a key distinction. If the problem is to recognize the language 3-SAT, then the enumerate all programs solution in the other thread might work. However, whether P=NP implies that co-3-SAT is also recognizable is the question I've been wrestling with.     There is another problem I have with the enumerative solution, which maybe I'll post in the other thread. « Last Edit: Nov 8th, 2003, 4:01pm by william wu » IP Logged [ wu ] : http://wuriddles.com / http://forums.wuriddles.com Rezyk Junior Member     Gender: Posts: 85 Re: 3SAT and P=NP   « Reply #5 on: Nov 8th, 2003, 4:09pm » Quote Modify P=NP does mean that co-3-SAT is polytime recognizable. (more in the other thread) IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board