Complexity Explorer Santa Fe Institute

Introduction to Computation Theory

Lead instructor: Josh Grochow

Your progress is not being saved! Enroll now or log in to track your progress or submit homework.

8.4 Unit Quiz » Quiz

Quiz scores are NOT recorded.

  • You may come back to quizzes and take them as many times as you like
  • When you are finished, clicking the "Score" button at the bottom of the test will show you the correct responses.

Question 1

Given a function $f$​​​​​​​ which takes a finite string as input and produces a finite string as output, a randomized Turing machine M is defined to compute  if, for any input string x, , where the probability here is taken with respect to the coins flipped by M on input x. For deterministic functions from finite strings to finite strings, randomized Turing machines can compute some function that ordinary Turing machines cannot. 

Question 2

Randomized algorithms are always faster than deterministic algorithms.

Question 3

Randomized algorithms are always simpler, therefore easier to code

(without making as many programming errors).

Question 4

In most computers, the  function (or the equivalent in your favoriteprogramming language) produces:

Question 5

If ​​​​​​​, then the hardness versus randomness principle implies that

good psuedo-random generators exist, and therefore that $\mathsf{BPP} = \mathsf{P}$​​​​​​​.