MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 5 Mcqs, each offering curated multiple-choice questions to sharpen your Automata Theory knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
Which of the following are not in NP? |
| A. | All problems in P |
| B. | Boolean Satisfiability problems |
| C. | Integer factorization problem |
| D. | None of the mentioned |
| Answer» E. | |
| 2. |
Which of the following can be used to define NP complexity class? |
| A. | Verifier |
| B. | Polynomial time |
| C. | Both Verifier and Polynomial time |
| D. | None of the mentioned |
| Answer» D. None of the mentioned | |
| 3. |
In terms of NTIME, NP problems are the set of decision problems which can be solved using a non deterministic machine in _______ time. |
| A. | O(n) |
| B. | O(n<sup>1/2</sup>) |
| C. | O(n<sup>k</sup>), k N |
| D. | None of the mentioned |
| Answer» D. None of the mentioned | |
| 4. |
Which of the following is incorrect for the given phrasePhrase : solvable by non deterministic algorithms in polynomial time |
| A. | NP Problems |
| B. | During control flow, non deterministic algorithm may have more than one choice |
| C. | If the choices that non deterministic algorithm makes are correct, the amount of time it takes is bounded by polynomial time. |
| D. | None of the mentioned |
| Answer» E. | |
| 5. |
State true or false?Statement: If a problem X is in NP and a polynomial time algorithm for X could also be used to solve problem Y in polynomial time, then Y is also in NP. |
| A. | true |
| B. | false |
| Answer» B. false | |