f

#### Is the number guessing problem NP?

```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  aytasato
10/16/2016 5:32:41 PM comp.theory  5139 articles. 1 followers. 1 Replies 573 Views Similar Articles

[PageSpeed] 29

```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  Kaz
10/16/2016 6:17:36 PM