Problem Detail: this is my first question on this site. I recently, study on NP. I have some confusion about this Topic, and want to propose my inference and some one verify me.
I) each NP problem can be solved in Exponential Time. II) if P=NP then NP=NP-Complete. III) The following problem is in NP: given a natural number, determine whether it is the product of two prime factors. IV) if problem X can reduce to a known NP-Hard problem, then X must be NP-HARD.
anyone can verify my inference and learn me?
Asked By : Mino Jende
Answered By : Yuval Filmus
If you define exponential time as $O(2^{n^k})$ for some $k$, then (i) is correct. (ii) is almost correct – you have to exclude trivial problems (those in which all instances are yes instances or all instances are no instances). What you describe (iii) is not quite a decision problem, so as stated it is not strictly true. The language consisting of all tuples $(n,k,i,b)$ such that the $k$th smallest prime factor of $n$ has $i$th bit equal to $b$ is in NP. (iv) is incorrect – the empty language, for example, reduces to all NP-hard problems, but is not NP-hard itself. If some NP-hard problem Q reduces to a problem X then X is NP-hard: indeed any problem in NP reduces to Q (by definition of NP-hard), and through your reduction to X, and so by definition X is NP-hard.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/40441 Ask a Question Download Related Notes/Documents
