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. 0 followers. marty.musatov (1143) is leader. Post Follow

1 Replies
175 Views

Similar Articles

[PageSpeed] 7

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
Reply: