Riddle: I am a class of problems that can be verified in polynomial time, but my solutions might take a superpolynomial time to find. What am I? | Card: 5 / 20 |
A problem is in class P if it can be solved in time ______, where n is the size of the input and k is a constant. | Card: 7 / 20 |
Which of the following problems is NOT NP-complete? A) Hamiltonian Cycle B) Vertex Cover C) Bubble Sort D) Traveling Salesman Problem | Card: 9 / 20 |
![]() Unlock all Flashcards with EduRev Infinity Plan Starting from @ ₹99 only |
Fill in the blanks: A problem is NP-hard if every ______ problem can be reduced to it in polynomial time. | Card: 15 / 20 |
In complexity theory, a problem is said to be P-complete if it is both P and ______. | Card: 19 / 20 |






