Design and Analysis of Algorithms

Which one is true of the following
(i) all NP hard problems are NP complete
(ii) all NP complete problems are NP hard
(iii) some NP complete problems are NP hard
(iv) None of these

Which complexity class contains problems for which a given solution can be verified in polynomial time by a deterministic Turing machine?

(i) Class P
(ii) Class NP
(iii) Class NP-Hard
(iv) Class Undecidable

Which one of the following statement is correct?
(i) If $A \le_p B$ and $B \in P$ then $A \in P$
(ii) If $A \le_p B$ and $A
otin P$then$B
otin P$
(iii) If $A \le_p B$ and $B \le_p C$ then $A \le_p C$
(iv) All of these

What is the primary technique used to prove that a problem is NP-complete?
(i) Divide and conquer
(ii) Dynamic programming
(iii) Polynomial-time reduction from a known NP-complete problem
(iv) Space complexity calculation

What is the relationship between NP and P complexity classes?
(i) P is a subset of NP
(ii) NP is a subset of P
(iii) P and NP are equivalent
(iv) P and NP are disjoint sets

The Quantified Boolean Formula problem is a canonical complete problem for which of the following complexity classes?

(i) NP
(ii) P
(iii) PSPACE
(iv) co-NP

Write and explain the Cook's theorem.

Compare NP-hard and NP-completeness?

Define P-Class, NP-class, NP-complete class and NP-hard class of problems. What is the relation between them?

What is P, NP, NP hard, and NP complete? Write the relationship between all of them.

Answer the following:
(i) Describe complexity classes P, NP, NP-complete, and NP-hard.
(ii) State and explain Cook's Theorem.
(iii) Why is it considered a foundational result in computational complexity theory?

Answer the following:
(i) What is polynomial-time reduction?
(ii) How is it used to prove that a problem is NP-complete?
(iii) Explain the process of reducing 3-SAT to Vertex Cover.