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