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