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