 |  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 |
