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