Preview

01 - CS Unsolved Problems

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

  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.

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

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

 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.

  TRUE

  FALSE

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

  an algorithm that is neither time or space bound.

  mechanical application of mathematical steps, such as an algorithm.

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

  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).

  memory

  random access memory

  time

  data processing

 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).

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

  polynomial

  linear

  quadratic

 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.

  Cryptography

  Big Data Processing

  Data mining

  Graph theory

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

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

  an error (if it fails to compute)

   "yes" or "no"

  a number between 1 and 2 billion.

 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.

   NP-complete

  solvable without storage restructions

  NP = P

  UP-complete

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

  "Is P a subset of NP?"

  "Is P solvable?"

  "Is P = 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 _________.

  the limitations of finite memory are ignored.

  they are capable of solving problems in linear time.

  they are capable of using an unlimited amount of storage .

  the limitation of space and polynomial time is 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 ____.

   f(n).

  n(f).

  f(m)

  m(n)

 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

  Einstien

  Hilbert

  Riemann

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

  deleted

  verified

  backtracked

  plotted

 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.

  two-way function

  one-way function

  three-way function

  infinite function


Report an error