Preview

01 - CS Unsolved Problems

 1. A problem in computer science is considered unsolved when ______________________________.
unsolvedproblems_bulb_cert.png

  the time taken to solve the problem is too short (i.e it lasts for less than a second) to be tested.

  a solution is known but there is not enough storage space present to test the solution.

  a theory appears to have been solved and tested but another theory rises to contradict it.

  no solution is known, or when experts in the field disagree about proposed solutions.

 2. The Riemann hypothesis is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute; each carries a US$1,000,000 prize for the first correct solution.

  FALSE

  TRUE

 3. A computational problem is a task solved by a computer. A computation problem is solvable by ______________________________.
computingunsolvedprobs_cert_mystery.jpg

  a computer that is operating with the use of quibts not ordinary binary (bits).

  an algorithm that is neither time or space bound.

  mechanical application of mathematical steps, such as an algorithm.

  a human being replicating an algorithm in its brain.

 4. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. Fill in the blanks for the following: 
Computational complexity theory: This theory seeks to introduce 
mathematical models of computation to study these problems and 
quantify their computational complexity, i.e., the amount of resources 
needed to solve them, such as ____ and storage. 

Other measures of complexity are also used, such as the amount 
of communication (used in communication complexity), the number
of gates in a circuit (used in circuit complexity) and the number
of processors (used in parallel computing).

  data processing

  random access memory

  memory

  time

 5. The P versus NP problem asks whether every problem whose solution can be quickly verified (technically, verified in ________ time) can also be solved quickly (again, in ___________ time).

  linear

  polynomial

  quadratic

  t/2 (where t =time taken to solve the problem)

 6. ___________ relies on certain problems being difficult. A constructive and efficient solution to an NP-complete problem such as 3-SAT would break most existing __________ systems.

  Data mining

  Big Data Processing

  Cryptography

  Graph theory

 7. Conceptually speaking, a decision problem is a problem that takes as input some string w over an alphabet ?, and outputs ___________.

  an error (if it fails to compute)

  a number between 1 and 2 billion.

  a number that is divisible by 2 (for binary based machines).

   "yes" or "no"

 8. A problem is ___________ when it can be solved by a restricted class of brute force search algorithms and it can be used to simulate any other problem with a similar algorithm.

  solvable without storage restructions

  UP-complete

   NP-complete

  NP = P

 9. "Are quantum computers more powerful than classical computers?" could also be stated in the following way:

  "Is P solvable?"

  "Is P = NP?"

  "Is P a subset of NP?"

   "Is BQP a subset of P?"

 10. For a long time, one of the most famous problems known to be in BPP but not known to be in P was the problem of determining whether a given number is prime.This problem is still unsolved (not in P). 
Note: In computational complexity theory, bounded-error 
probabilistic polynomial time (BPP) is the class
 of decision problems solvable by a probabilistic
 Turing machine in polynomial time with an error
 probability bounded away from 1/3 for all instances.

  FALSE

  TRUE

 11. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete if _________.

  they are capable of solving problems in linear time.

  the limitation of space and polynomial time is ignored.

  they are capable of using an unlimited amount of storage .

  the limitations of finite memory are ignored.

 12. A Turing machine M is said to operate within time f(n), if the time required by M on each input of length n is at most ____.

  m(n)

  f(m)

   f(n).

  n(f).

 13. The _______hypothesis is a conjecture that the ________ zeta function has its zeros only at the negative even integers and complex numbers with real part 1/2. Many consider it to be the most important unsolved problem in pure mathematics.

  Goldbach

  Riemann

  Hilbert

  Einstien

 14. Although a solution to an NP-complete problem can be _________"quickly", there is no known way to find a solution quickly.

  deleted

  plotted

  verified

  backtracked

 15. In computer science, a ___________ is a function that is easy to compute on every input, but hard to invert given the image of a random input.

  three-way function

  infinite function

  one-way function

  two-way function


Report an error