Given an unsorted array of size n, it's obvious that finding whether an element exists in the array takes O(n) time.
If we let h = log n then it takes O(2^h) time.
Notice that if the array is sorted, a binary search actually takes O(h) time (which is polynomial) but the binary search cannot apply to an unsorted array.
Is it possible to prove that the problem to find an element in an array (yes or no) is NP complete in terms of h. What problem should I reduce from and how to reduce?
A more formal definition of the problem is given below.
We have an oracle, which is a binary tree of height h with each node having random values. I.E. a tree that DOES NOT have the property that all values in the left subtree of a node must be smaller than the value in the node or all values in the right subtree of a node must be greater than the value in the node. However all nodes in the oracle tree are guaranteed to have value between 0 and 2^h-1.
The input is a number to be searched. The input is guaranteed to have value between 0 and 2^h-1. (The input has h bits)
(Let's say we are searching through the same array every time and hence we have the same oracle every time so the tree itself is not a part of input.)
The output is YES or NO, indicating whether the input is in a node of the tree or not.
Question: whether this problem is NP complete or not in terms of h. This problem is NP because if a path to the YES node in the tree is given it can be verified in O(h) time.
Assuming NP != P, since the problem is in NP it must be either NP-complete or P (Apparently there is something called NP-intermediate (credited to Nicholas) so that's another possibility as well). If it is NP-complete, what problem can be used to reduce to this problem?
Note that if the oracle tree has the property that left subtree of a node is less than the node and right subtree of a node is greater than the node then the problem is in P and NOT in NP complete because binary search can be applied.
Intuitively, this problem can be viewed as a non-deterministic turing machine and every single possible path needs to be considered but this intuition cannot be used to "prove" the problem is NP complete. I want to know if we can reduce any known NP-complete problem to it.
Reference: (Original Post) https://stackoverflow.com/questions/28847966/array-search-np-complete