|
 Undecidability 20 Flashcards |
Start
|
|
What is the time complexity of quick sort? |
Card: 1 / 20 |
|
|
Θ(n log n) |
Card: 2 / 20 |
|
|
True or False: All problems in class P can be solved in exponential time. |
Card: 3 / 20 |
|
|
False. Problems in class P can be solved in polynomial time. |
Card: 4 / 20 |
|
|
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 |
|
|
NP (Nondeterministic Polynomial time) |
Card: 6 / 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 |
|
|
Θ(n^k) |
Card: 8 / 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 |
|
|
C) Bubble Sort |
Card: 10 / 20 |
|
|
 Unlock all Flashcards with EduRev Infinity Plan Starting from @ ₹99 only
|
|
|
|
True or False: The emptiness problem for context-free grammars is P-complete. |
Card: 11 / 20 |
|
|
True. |
Card: 12 / 20 |
|
|
What is the time complexity of matrix multiplication algorithm? |
Card: 13 / 20 |
|
|
Θ(n³) |
Card: 14 / 20 |
|
|
Fill in the blanks: A problem is NP-hard if every ______ problem can be reduced to it in polynomial time. |
Card: 15 / 20 |
|
|
NP |
Card: 16 / 20 |
|
|
Riddle: I am a set of vertices in a graph, covering all edges. What am I? |
Card: 17 / 20 |
|
|
Vertex Cover |
Card: 18 / 20 |
|
|
In complexity theory, a problem is said to be P-complete if it is both P and ______. |
Card: 19 / 20 |
|
|
P-hard |
Card: 20 / 20 |
|
|
Completed! Keep practicing to master all of them. |
Restart
|
