Theory of Computation Solutions to HW-4 (10 points) Exercise 1 (1 pt for each co

Question

Theory of Computation Solutions to HW-4 (10 points) Exercise 1 (1 pt for each correct answer). For each of the following statements indicate 1. If a problem can be solved in exponential time, it can also be solved in polynomial 2. If a problem can be solved by a polynomial-time nondeterministic Turing machine, it 3. If a problem can be solved by a polynomial-time nondeterministic Turing machine, it 4. If a problem can be solved by an exponential-time deterministic Turing machine, it whether it is true, false, or unknown time. can also be solved by a polynomial-time deterministic Turing machine. can also be solved by an exponential-time deterministic Turing machine. can also be solved by a polynomial-time nondeterministic Turing machine.

Explanation / Answer

Solution:

1)

Unknown

Explanation:

We cannot say if there are any polynomial time algorithm for that. we may use dynamic programming to reduce the running time of the algorithm.

2)

Unknown.

3)

True.

4)

False, we cannot say that.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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