0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ "Assuming NP != P, since the problem is in NP it must be either NP-complete or P". That is categorically false--see Ladner's theorem. $\endgroup$ – Nicholas Mancuso Mar 9 '15 at 6:54
  • $\begingroup$ Thank you for the comment. So this problem actually has possibility to be a NP-intermediate problem? I still think it is NP complete based on the intuition though. $\endgroup$ – cr001 Mar 9 '15 at 7:14
  • 3
    $\begingroup$ I think the issue here is a lack of command of the fundamentals; see our reference material. $\endgroup$ – Raphael Mar 9 '15 at 8:38
  • $\begingroup$ Please don't cross-post on multiple SE sites; that is forbidden by site rules, and it is impolite to answerers as it fragments discussion. $\endgroup$ – D.W. Mar 9 '15 at 16:56
5
$\begingroup$

If you want to prove that a problem is NP-complete, you don't get to make up your own definition of NP. NP is the class of problems that can be solved by a nondeterministic Turing machine in time bounded by some polynomial function of the length of the input.

Specifically, you don't get to use oracles, you don't get to use some other measure of the size of the input (e.g., the logarithm of its length) and you don't get to make random access to the contents array: you have to walk the head of the Turing machine there, one cell at a time.

Your problem is, as you say in your first sentence, clearly in P. It is, therefore, very unlikely to be NP-complete, since that can only happen if P=NP.

$\endgroup$
  • $\begingroup$ If oracles are not allowed, does it mean any binary-tree related problem cannot be NP-complete? To me a tree is really similar to a non-deterministic Turing machine and I wanted to somehow connect the concepts together. Is there a formal way to prove that there cannot be an algorithm that is faster than exponential time for some arbitrary tree-traversal decision problem? (Have to visit every single node vs. only need to go through one path) $\endgroup$ – cr001 Mar 10 '15 at 2:32
  • 1
    $\begingroup$ Sure, binary tree problems can be NP-complete: that has nothing to do with oracles. Tree-traversals are linear time because they visit every node of the tree exactly once, with constant overhead per node. Remember that complexity is measured with respect to the input size, which is the number of bits required to represent the tree, not its depth. $\endgroup$ – David Richerby Mar 10 '15 at 8:07
  • $\begingroup$ Thanks, I understand what you are trying to say but what I am asking is the following: "Does it mean I cannot relate the concept of NP completeness or non-deterministic Turing machine to the problem of whether I can traverse a tree polynomially with respect to its height?" In my mind they really looks similar to me. $\endgroup$ – cr001 Mar 11 '15 at 1:43
  • 1
    $\begingroup$ Intuatively, the big difference between tree transversal and non-determistic turing machines, is with tree transversal you start with the tree (it is part of the input). If you are considering doing a tree-like search to explore how a non-deterministic turing machine will operate, then you don't start with the tree, and the tree can be very large in relation to the size of the turing machine description. $\endgroup$ – Chris Jefferson Mar 13 '15 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.