In: Computer Science
(e) T F The set of all NP-hard problems is the same as the set of all NP-complete problems.
(f) T F The dynamic programming technique can be used to solve any optimization problem.
(g) T F If A ≤p B and A is NP-Complete, then B is also NP-Complete.
(h) T F If a problem is in P, then it can be solved in polynomial time nondeterministically
with brief explaination
Answer:----------
(e) T F The set of all NP-hard problems is the same as the set
of all NP-complete problems.
False, NP-Complete set is a subset of NP-Hard set and A
problem is NP-Complete iff it is NP-Hard and it is in NP
itself.
(f) T F The dynamic programming technique can be used to solve
any optimization problem.
False, because Dynamic programming (DP) can be used to
solve certain optimization problems. For example Rod
Cutting, Chained Matrix Multiplication
etc.
(g) T F If A ≤p B and A is NP-Complete, then B is also
NP-Complete.
True,
Proof:-
Let f be a polynomial-time reducibility function from A to B.
Let M be a polynomial-time nondeterministic TM that decides
A.
NTM M′ to decide membership in B:
On input w:
• Compute x = f(w); |x| is bounded by a polynomial in |w|.
• Run M on x and accept/reject (on each branch) if M does.
– Polynomial time-bounded NTM.
– Decides membership in B:
• M′ has an accepting branch on input w
iff M has an accepting branch on f(w), by definition of M′,
iff f(w) ∈ A, since M decides A,
iff w ∈ B , since A ≤p B using f.
– So M′ is a poly-time NTM that decides B, B∈ NP.
(h) T F If a problem is in P, then it can be solved in
polynomial time nondeterministically.
False, because If a problem is in P, then it can be solved
in polynomial time deterministically.