Is unsorted DB searching in NP?

From: d. lee (donghunlee8_at_hotmail.com)
Date: 07/20/04 

Date: 20 Jul 2004 05:48:43 -0700

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?
 2. Is this EXP (which is not P) ?
 3. according to 1 &2
     can we say NP!=P?

Thank you many times.

Relevant Pages

  • Re: searching for missing element in an array
    ... "Suppose we have n numbersand there is an array of size ... which number is missing from the array if ... there are n-1 numbers present. ... which is implied by the phrase "which number is missing" ...
    (comp.programming)
  • Re: Sorting arrays
    ... you could set up a rank N-1 array, and bin your samples as you go ... you won't have to write a sort ... are indexes of a co-ordinate in a N-1 dimensional space and the Nth ...
    (comp.lang.fortran)
  • Sorting arrays
    ... Each row of my array is made up of N columns. ... are indexes of a co-ordinate in a N-1 dimensional space and the Nth ... I want to sort the array so that the first coordinate is sorted ...
    (comp.lang.fortran)
  • Re: searching for missing element in an array
    ... What happens if the array was initialized to all -1 values? ... we know that a zero is stored in the slot of the missing number? ... initialization of the array. ... that there are n-1 numbers present. ...
    (comp.programming)
  • Re: Confusing Runtime Error.
    ... an array of dimension n has elements 0 to n-1. ... IchBin, Pocono Lake, Pa, USA http://ichbinquotations.awardspace.com ...
    (comp.lang.java.help)