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?

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.