A) Analyzing the resources required to solve computational problems B) Hardware design for computers C) Developing new programming languages D) Psychological aspects of human-computer interaction
A) Big O notation B) Binary code C) Roman numerals D) Greek letters
A) EXP B) BPP C) NP D) PSPACE
A) To build supercomputers B) To generate random numbers C) To create faster computers D) To classify computational problems based on their inherent difficulty
A) BPP B) NP-complete C) P D) EXPTIME
A) Exponential time B) Expanded C) Expert D) Exploratory
A) P vs NP problem B) Parallel computing C) NP-completeness D) Quantum algorithms
A) PSPACE B) NP-complete C) BQP D) EXPSPACE
A) An unsolvable theoretical question B) A mathematical equation that cannot be solved C) A task solved by a computer using an algorithm D) A hardware issue in computers
A) The binary alphabet {0,1} B) The set of all lowercase letters C) The set of ASCII characters D) The hexadecimal alphabet
A) Some concrete choice of input encoding B) Encoding using natural language C) Use of decimal notation only D) No need for any encoding
A) Deciding whether a given graph is connected or not. B) Finding the shortest path in a graph. C) Determining the number of nodes in a graph. D) Calculating the maximum flow in a network.
A) Checking if a graph is bipartite. B) Deciding if a number is prime. C) The traveling salesman problem. D) Determining if two graphs are isomorphic.
A) Words B) Characters C) Bytes D) Bits
A) An early form of computer hardware. B) A theoretical model for general computation. C) A device to manipulate physical objects. D) A practical computing technology.
A) P vs NP theorem. B) The Church–Turing thesis. C) Gödel's incompleteness theorems. D) Cook-Levin theorem.
A) Probabilistic Turing machine. B) Quantum Turing machine. C) Non-deterministic Turing machine. D) Deterministic Turing machine.
A) They require physical realizability. B) They use random bits for computation. C) They are limited to polynomial time. D) They operate deterministically.
A) Blum complexity axioms B) Turing completeness axioms C) P vs NP axioms D) Cook-Levin theorem
A) Quantum entanglement complexity B) Decision tree complexity C) Communication complexity D) Circuit complexity
A) Circuit complexity B) Time complexity C) Space complexity D) Communication complexity
A) Real-time computations B) Linear bounded automata C) Rudimentary sets D) Complexity measures
A) Cook-Levin theorem B) Savitch's theorem C) P vs NP problem D) Time hierarchy theorem
A) AC B) BPP C) NC D) QMA
A) Time hierarchy theorem B) Space hierarchy theorem C) Savitch's theorem D) Cook-Levin theorem
A) 1960 B) 1955 C) 1956 D) 1971
A) BQP B) MA C) PH D) PP
A) Christos Papadimitriou B) Oded Goldreich C) Michael R. Garey; David S. Johnson D) Sanjeev Arora; Boaz Barak
A) 1967 B) 1972 C) 1971 D) 1965
A) "Signalizing function" B) "Computational complexity" C) "Turing machine" D) "Polynomial time"
A) Linear-time reduction. B) Logarithmic-time reduction. C) Polynomial-time reduction. D) Exponential-time reduction.
A) 1965 B) 1936 C) 1945 D) 1950
A) Garey, Michael R.; Johnson, David S. B) Arora, Sanjeev; Barak, Boaz C) Wuppuluri, Shyam; Doria, Francisco A. D) Downey, Rod; Fellows, Michael
A) co-P would equal co-NP B) NP would not equal co-NP C) co-P would not equal co-NP D) P would not equal NP
A) AC B) QMA C) BPP D) RP
A) Gabriel Lamé B) Alan Turing C) Richard E. Stearns D) Juris Hartmanis
A) John Myhill B) Hisao Yamada C) Boris Trakhtenbrot D) Raymond Smullyan
A) L B) NC C) NL D) PP
A) EXPTIME B) NP C) PSPACE D) FP
A) Raymond Smullyan B) Hisao Yamada C) Boris Trakhtenbrot D) John Myhill
A) Continuous functions. B) Discrete graphs. C) Boolean expressions. D) Quantum states.
A) NP B) ALL C) EXPTIME D) P
A) Papadimitriou, Christos; Sipser, Michael B) Downey, Rod; Fellows, Michael C) Cook, Stephen; Fortnow, Lance D) Wuppuluri, Shyam; Doria, Francisco A.
A) 30 B) 21 C) 15 D) 10
A) Average-case complexity B) Worst-case complexity C) Amortized analysis D) Best-case complexity
A) BQP B) NP C) co-NP D) PP
A) Probabilistic algorithms. B) Continuous dynamical systems and differential equations. C) Digital signal processing. D) Finite state machines.
A) Fortnow, Lance; Homer, Steven B) Khalil, Hatem; Ulery, Dana C) Cook, Stephen D) Mertens, Stephan
A) IP B) BPP C) NC D) QMA
A) Sanjeev Arora; Boaz Barak B) Oded Goldreich C) Christos Papadimitriou D) Michael R. Garey; David S. Johnson
A) Leonid Levin B) Edmonds C) Juris Hartmanis D) Gabriel Lamé
A) Boaz Barak B) Sanjeev Arora C) Christos Papadimitriou D) Michael Sipser
A) NC B) RP C) #P D) BPP |