wu :: forums - Print Page


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

        riddles >> cs >> np complete problem
        
(Message started by: kirru on Nov 15^th, 2012, 9:00am)

Title: np complete problem
Post by kirru on Nov 15^th, 2012, 9:00am

Ram and Shyam have been asked to show that a certain problem PI is NP-complete. Ram shows a
polynomial time reduction from the 3-SAT problem to Pi and Shyam shows a polynomial time
reduction from PI to 3-SAT. Which of the following can be inferred from these reductions?
A. PI is NP-hard but not NP-complete
B. PI is in NP, but is not NP-complete
C. Pi is NP-complete
D. PI is neither NP-hard, nor in NP

Title: Re: np complete problem
Post by towr on Nov 23^rd, 2012, 8:00am

I'll go with C

Title: Re: np complete problem
Post by kirru on Nov 24^th, 2012, 7:01am

Dear Towr, how can we say that it is in NP?

Title: Re: np complete problem
Post by towr on Nov 24^th, 2012, 1:00pm

Because you can solve it in polynomial time on a non-deterministic machine via reduction to 3-SAT