Unit V 25.5.2021

Problems that can be solved in polynomial time are known as?

• intractable

• tractable

• decision

• complete

Which of the following is true 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

• All of the above

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

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.

_________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms.

• NP

• P

• Hard

• Complete

Problems that cannot be solved by any algorithm are called?

• tractable problems

• intractable problems

• undecidable problems

• decidable problems

Halting problem is an example for?

• decidable problem

• undecidable problem

• complete problem

• trackable problem

How many conditions have to be met if an NP- complete problem is polynomially reducible?

• 1

• 2

• 3

• 4

Which of the following problems is not NP complete?

• Hamiltonian circuit

• Bin packing

• Partition problem

• Halting problem

The problem 3-SAT and 2-SAT are

• both in P

• both NP complete

• NP-complete and in P respectively

• undecidable and NP-complete respectively