DAA_NP COMPLETE

Which of the following is false about NP-Complete and NP-Hard problems.

• If we want to prove that a problem X is NP-Hard, we take a known NP-Hard problem Y and reduce Y to X

• The first problem that was proved as NP-complete was the circuit satisfiability problem.

• NP-complete is a subset of NP Hard

• None of the above

Which of the following statements are TRUE?

(1) The problem of determining whether there exists a cycle in an undirected graph is in P.

(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.

(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

• 1 and 3

• 2 and 3

• 1 and 2

• All the three

Let X be a problem that belongs to the class NP. Then which one of the following is TRUE?

• There is no polynomial time algorithm for X.

• If X can be solved deterministically in polynomial time, then P = NP.

• If X is NP-hard, then it is NP-complete.

• X may be undecidable.

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

• R is NP-complete

• R is NP-hard

• Q is NP-complete

• Q is NP-Hard

Problems that cannot be solved by any algorithm are called

To which class does the Euler’s circuit problem belong?

• P

• NP

• NP Hard

• NP Complete

How many stages of procedure does a non-deterministic algorithm consist of?

• 1

• 2

• 3

• 4

A non-deterministic algorithm is said to be non-deterministic polynomial if the time-efficiency of its verification stage is polynomial.

• True

• False

Problems that can be solved in polynomial time are known as traceable problems

• True

• False

CNF-satisfiability problem belongs to

• P

• NP

• NP HARD

• NP COMPLETE