Say about all these statements if they are true or not or are an open problem. P

Question

Say about all these statements if they are true or not or are an open problem. Prove, or explain precisely your answer.

1. If P = NP then the Halting problem becomes decidable.

2. If NP 6= Co NP then P 6= NP. Hint: think what is the complement of P

3. If we can solve the Hamiltonian path in time O(n 4 ) then you can solve any other NPC problem in O(n 4 ) time.

4. Say that the input contains 3 numbers a, b, c. Say that we have an algorithm for the problem that runs in time O(log2 a) + O( b) + O(log c). Is this algorithm polynomial?

Explanation / Answer

1)

TRUE

Since P = NP means it halts for every input. So on every input we can decide. So Halting problen becomes decidble.

-------------------------------------------------------------------------------------------------------------------------------------------------

2) TRUE

CO means completeness. It is combination of problems solve in polynomial time and non-polynomial time.

so, CO = P + NP ===> P = CO - NP

But given condition is NP != CO - NP .

So thos condition is true since they said not equal.

---------------------------------------------------------------------------------------------------------------------------------------------------

3) FALSE

Hamilton path is done in O(n4) time. So it not intends to say all other NPC solve in same time.

-----------------------------------------------------------------------------------------------------------------------------------------------------

4) Yes it is solve in polynomial time. Since a ,b, c are numbers and defined. So we will have definite solution in polynomial time.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.