Re: Is unsorted DB searching in NP?
From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 07/20/04
- Next message: Mitch Harris: "Re: Disproof of the Halting Problem's Conclusion"
- Previous message: Hans Hüttel: "Re: accepting vs. recognizing"
- In reply to: d. lee: "Is unsorted DB searching in NP?"
- Next in thread: David Wagner: "Re: Is unsorted DB searching in NP?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Tue, 20 Jul 2004 15:56:21 +0200
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?
- what is your input data? the array A? its size N? or just
the integer n (the log of N)? I guess it is A and N. n is
just a secondary thing.
could ask whether it is in NP. the closest rewording I can
figure is
"Given A and i, is A[i] = 1?"
or possibly
"Given A and k, is there an i < k such that A[i] = 1?"
To tell what complexity class this is in, it'd still be
nicer to translate a little more (make a graph problem out
of it).
I highly suspect it is way down the complexity hierarchy
(say in L (logspace complete)) but I have no reduction in
mind.
> 2. Is this EXP (which is not P) ?
- EXP is a complexity class of -decision- problems. same
difficulty as #1.
- if I guess your real question is "Is this an exponential
algorithm?", then no, because I can give a linear time
algorithm (an algorithm that takes time proportional to the
input size N): scan the array in order, return i, when you
find A[i] = 1.
> 3. according to 1 &2
> can we say NP!=P?
No.
-- Mitch Harris (remove q to reply)
- Next message: Mitch Harris: "Re: Disproof of the Halting Problem's Conclusion"
- Previous message: Hans Hüttel: "Re: accepting vs. recognizing"
- In reply to: d. lee: "Is unsorted DB searching in NP?"
- Next in thread: David Wagner: "Re: Is unsorted DB searching in NP?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
