CSE
|
Civil
|
ECE
|
EE
|
ME
About GATE
About GATE
GATE Papers
GATE Exam History
GATE 2020
GATE 2020 Poster
Important Dates
Application Fees
Application Form Filling
Eligibility Criteria
Exam Centres & Cities
Degree Qualifying Discipline
Exam Schedule
Online Mock Exam
Exam Pattern & Marking Scheme
Calculate GATE Score
Helpdesk Number & Contacts
GATE 2020 FAQs
GATE Exams
GATE 2020
GATE 2019
GATE 2018
GATE 2017
GATE 2016
GATE 2015
GATE 2014
GATE 2013
GATE 2012
Syllabus
Papers
Weightage
Books
Admission
Coaching
PSUs
About Us
Disclaimer
Privacy Policy
Contact Us
GATE Papers >> CSE >> 2009 >> Question No 14
Question No. 14
CSE
|
GATE 2009
Let
π
A
be a problem that belongs to the class NP. Then which one of the following is TRUE?
(A)
There is no polynomial time algorithm for
π
A
.
(B)
If
π
A
can be solved deterministically in polynomial time, then P = NP.
(C)
If
π
A
is NP-hard, then it is NP-complete.
(D)
π
A
may be undecidable.
Answer :
(C) If
π
A
is NP-hard, then it is NP-complete.
Previous
Next
GATE 2009
CSE
Algorithms
Basic concepts of complexity classes – P, NP, NP-hard, NP-complete
Comments
No Comments
Leave a comment
*
Name
*
Email
*
Comment
Go
Loading...