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