Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

Home / Engineering / Theory of Computation / Question

Mr. Dubey • 51.47K Points
Coach

Q.) Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

(A) Both DHAM3 and SHAM3 are NP-hard

(B) SHAM3 is NP-hard, but DHAM3 is not

(D) Neither DHAM3 nor SHAM3 is NP-hard

Correct answer : Option (A) - Both DHAM3 and SHAM3 are NP-hard

Discusssion

Related MCQs on Theory of Computation

Q. Business Risk affects The Organization developing or Procuring the software.

Q. Which of the following doesn't include in message types?

Q. An operational system is _____________.

Q. Which of the following statements is correct about constructors?

Q. Which statement(s) about IPv6 addresses are true?

Q. The operation that does not involves clock cycles is

Q. ………..models in which the input and output variables follow a probability distribution.

Q. What is the space complexity of program to reverse stack recursively?

Q. Which family of devices has the characteristic of preventing saturation during operation?

Q. A fact is said to be partially additive if_______.