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