Suppose I have a machine that performs a linear search on integers 1 to M a= nd by compare each to a number chosen non-deterministically (i.e. randomly = by some factor external to the system). If M=3Dpoly(n), does that mean that since we have M possible values to comp= are to, for which each comparison takes O(n) time, we can possibly search M= =E2=88=97poly(n) times with a deterministic machine or just poly(n) using a= non-deterministic machine?

0 |

10/16/2016 5:32:41 PM

On 2016-10-16, aytasato@gmail.com <aytasato@gmail.com> wrote: > Suppose I have a machine that performs a linear search on integers 1 > to M and by compare each to a number chosen non-deterministically > (i.e. randomly by some factor external to the system). > > If M=poly(n), does that mean that since we have M possible values to You have a free variable n here. Without pinning down what it represents, the rest of the text is meaningless.

0 |

10/16/2016 6:17:36 PM