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