Reputation: 21
Here is the context of the question: For each of the following statements, indicate whether it is true, false, or unknown, where 'unknown' indicates that scientists have not conclusively determined whether the statement is true or false. For example, the correct answer for the statement P=NP is unknown. But the correct answer for the best algorithm for the maximum flow problem in n-vertex graphs takes time at least 2^n'' is ``false''.
Give a short justification for your answer (i.e. explain why the statement is true, or false, or not known to be either true or false).
And here is the statement I am unsure: Some N P -complete problems have polynomial time algorithms, but some others do not..
I came up with two solutions which I think both make sense to me:
Unknown:If any NP-complete problem can be solved by a polynomial time algorithm, then all of them can be by the reduction. So NP = P OR False: if some NP-complete algorithms have polynomial time algorithms, we can reduce them to the NP-complete problems which don’t have polynomial time algorithms, which means they have polynomial time algorithms as well.
I wonder which is true.
Upvotes: 1
Views: 133