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