wu :: forums - Print Page


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

        riddles >> cs >> 3SAT and P=NP
        
(Message started by: Dudidu on Nov 6^th, 2003, 9:55am)

Title: 3SAT and P=NP
Post by Dudidu on Nov 6^th, 2003, 9:55am

Assuming P=NP (:P), suggest a deterministic polynomial time algorithm that finds a satisfying assignment for a given 3SAT.

Title: Re: 3SAT and P=NP
Post by william wu on Nov 6^th, 2003, 12:13pm

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

Title: Re: 3SAT and P=NP
Post by Dudidu on Nov 8^th, 2003, 12:01pm

on 11/06/03 at 12:13:32, 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 ;D...
(or unfortunatly I will be obligated to do it :'()

Title: Re: 3SAT and P=NP
Post by Rezyk on Nov 8^th, 2003, 1:41pm

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.

Title: Re: 3SAT and P=NP
Post by william wu on Nov 8^th, 2003, 3:56pm

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.

Title: Re: 3SAT and P=NP
Post by Rezyk on Nov 8^th, 2003, 4:09pm

P=NP does mean that co-3-SAT is polytime recognizable. (more in the other thread)