TRE 4 Theory of computations Practice set 1 06th November 2026 Share On Que: (1). Which of the following is NOT an NP-Complete problem? Asked in BPSC TRE 3.0 Shortest Path Problem C. Boolean Satisfiability Problem B. Traveling Salesman Problem A. More than one of the above D. None of the above E. Check Answer Open question page Que: (2). Which of the following classes contains problems that can be solved in polynomial time? NP A. NP-Hard B. P C. More than one of the above D. None of the above E. Check Answer Open question page Que: (3). What is the defining characteristic of an NP problem? It cannot be solved by a computer C. A proposed solution can be verified in polynomial time B. It can always be solved in constant time A. More than one of the above D. None of the above E. Check Answer Open question page Que: (4). Which theorem established Boolean Satisfiability (SAT) as the first NP-Complete problem? Cook-Levin Theorem B. Bayes Theorem C. Poincare Theorem A. More than one of the above D. None of the above E. Check Answer Open question page Que: (5). Which of the following is an example of an NP-Hard problem? Optimization version of Traveling Salesman Problem C. Binary Search A. Minimum Spanning Tree B. More than one of the above D. None of the above E. Check Answer Open question page Que: (6). Which condition must be satisfied for a problem to be NP-Complete? It must be solvable in constant time C. It must belong to P only A. It must belong to NP and be NP-Hard B. More than one of the above D. None of the above E. Check Answer Open question page Que: (7). Which of the following is a polynomial-time algorithm for finding the shortest path in a graph with non-negative edge weights? Exhaustive Search C. Dijkstra Algorithm A. Brute Force Algorithm B. More than one of the above D. None of the above E. Check Answer Open question page Que: (8). If any one NP-Complete problem is solved in polynomial time, what will be the consequence? Only that problem will belong to P A. NP will become empty C. P will be equal to NP B. More than one of the above D. None of the above E. Check Answer Open question page Que: (9). Which of the following problems is a well-known NP-Complete decision problem? Finding the maximum element in an array C. Graph Coloring with at most 3 colors A. Binary Search B. More than one of the above D. None of the above E. Check Answer Open question page Que: (10). Which of the following statements about NP-Hard and NP-Complete problems is correct? Every NP-Hard problem must belong to NP A. Every problem in P is NP-Complete C. Every NP-Complete problem is NP-Hard B. More than one of the above D. None of the above E. Check Answer Open question page Que: (11). What is the computational complexity of the Halting Problem? Asked in BPSC TRE 3.0 O(1) A. O(n) B. Not computable C. More than one of the above D. None of the above E. Check Answer Open question page Que: (12). Who proved that the general Halting Problem is undecidable? John von Neumann C. Alan Turing B. Charles Babbage A. More than one of the above D. None of the above E. Check Answer Open question page Que: (13). A decision problem is called decidable when: It has no possible solution A. It can be solved only in exponential time B. An algorithm always terminates with the correct Yes or No answer C. More than one of the above D. None of the above E. Check Answer Open question page Que: (14). Which of the following is an example of an undecidable problem? Halting Problem C. Checking whether a number is prime A. Sorting a list of integers B. More than one of the above D. None of the above E. Check Answer Open question page Que: (15). What is the meaning of an undecidable problem in computer science? A problem that requires constant time A. A problem that requires linear time C. A problem that cannot be solved by any algorithm for all inputs B. More than one of the above D. None of the above E. Check Answer Open question page Que: (16). Which mathematical model is commonly used to study the Halting Problem? Pushdown Automaton C. Turing Machine B. Finite Automaton A. More than one of the above D. None of the above E. Check Answer Open question page Que: (17). Which of the following statements about decidable and undecidable problems is correct? Every decidable problem has an algorithm that halts on all valid inputs C. Every undecidable problem belongs to P A. Every decidable problem must be NP-Complete B. More than one of the above D. None of the above E. Check Answer Open question page Que: (18). What is the main technique used by Alan Turing to prove the undecidability of the Halting Problem? Proof by contradiction using diagonalization B. Binary Search A. Dynamic Programming C. More than one of the above D. None of the above E. Check Answer Open question page Que: (19). Which of the following problems is decidable? General Halting Problem A. Checking whether a given integer is even C. Post Correspondence Problem B. More than one of the above D. None of the above E. Check Answer Open question page Que: (20). Which of the following is true about the Halting Problem? It can be solved in polynomial time for all programs B. No general algorithm exists that correctly determines halting for every program and input C. It can be solved in O(1) time A. More than one of the above D. None of the above E. Check Answer Open question page Que: (21). Which of the following is NOT a component of a Turing Machine? Asked in BPSC TRE 3.0 Input tape A. Control unit C. Output tape B. More than one of the above D. None of the above E. Check Answer Open question page Que: (22). Who introduced the concept of the Turing Machine? John McCarthy C. Alan Turing B. Charles Babbage A. More than one of the above D. None of the above E. Check Answer Open question page Que: (23). What is the primary function of the read/write head in a Turing Machine? Only to write symbols B. Only to read symbols A. To read and write symbols on the tape and move along it C. More than one of the above D. None of the above E. Check Answer Open question page Que: (24). Which symbol is commonly used to represent a blank cell on the tape of a Turing Machine? B C. 1 B. 0 A. More than one of the above D. None of the above E. Check Answer Open question page Que: (25). What does the transition function of a Turing Machine determine? Only the number of tape cells C. Only the input string A. The next state, symbol to be written and head movement B. More than one of the above D. None of the above E. Check Answer Open question page Que: (26). Which of the following best describes the tape of a standard Turing Machine? A temporary input buffer only C. An infinite sequence of cells used for reading and writing B. A fixed-size memory register A. More than one of the above D. None of the above E. Check Answer Open question page Que: (27). What is the role of the finite control unit in a Turing Machine? To store unlimited data A. To provide an additional tape C. To control the machine state and determine transitions B. More than one of the above D. None of the above E. Check Answer Open question page Que: (28). Which of the following is the correct representation of a standard deterministic Turing Machine transition function? δ : Q × Γ → Q × Γ × {L, R} A. δ : Q → Γ B. δ : Γ → Q C. More than one of the above D. None of the above E. Check Answer Open question page Que: (29). Which of the following is true about the initial state of a Turing Machine? It must be the only state in the machine C. It is the state from which computation begins B. It is always the final state A. More than one of the above D. None of the above E. Check Answer Open question page Que: (30). Which of the following statements about a Universal Turing Machine is correct? It can solve every undecidable problem B. It can simulate the behavior of any Turing Machine given its description and input A. It does not require an input tape C. More than one of the above D. None of the above E. Check Answer Open question page
