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