Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that

Home / Engineering / Theory of Computation / Question

Mr. Dubey • 51.17K Points
Coach

Q.) Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that

(A) P is NP-complete

(B) P is NP-hard but not NP-complete

(D) P is neither NP-hard nor in NP

Correct answer : Option (A) - P is NP-complete

Discusssion

Related MCQs on Theory of Computation

Q. Fog computing can be perceived in and

Q. What is a Grouped Report?

Q. which of the following is not the array distribution method of data partitioning

Q. A ___________ model identifies patterns or relationships.

Q. Decentralised IT management system has

Q. _____ is any entity authorised or recognised by the Authority for the purpose of enrolling individuals through Enrolment Agency.

Q. Kaizen is a – process the purpose of which goes beyond simple productivity improvement.

Q. In serial data transmission, every byte of data is padded with a ‘0’ in the beginning and one or two ‘1’ s at the end of byte because

Q. Which SQL function is used to count the number of rows in a SQL query?

Q. Which of the following, in C++, is inherited in a derived class from base class?