Re: Is unsorted DB searching in NP?

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 07/20/04 

Date: Tue, 20 Jul 2004 15:20:59 +0000 (UTC)

d. lee wrote:
>Problem:
> An array A[i] ,i=1..N, (N=2^n)
>contains N-1 '0' and only one '1' in unsorted manner.
>Find i where A[i]=1.
>
>Question:
> 1. Is this problem in NP?

Yes. It can be solved in time linear in the size of the input, assuming
a standard encoding of the input A[1..N], hence it is in P, hence it is
in NP. No, this shows nothing about the P =? NP question.