Author |
Topic: np complete problem (Read 3158 times) |
|
kirru
Newbie
Posts: 34
|
 |
np complete problem
« on: Nov 15th, 2012, 9:00am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
kirru
Newbie
Posts: 34
|
|
Re: np complete problem
« Reply #2 on: Nov 24th, 2012, 7:01am » |
Quote Modify
|
Dear Towr, how can we say that it is in NP?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: np complete problem
« Reply #3 on: Nov 24th, 2012, 1:00pm » |
Quote Modify
|
Because you can solve it in polynomial time on a non-deterministic machine via reduction to 3-SAT
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print