6
$\begingroup$

For some problems, like sorting, we know that on a deterministic RAM Machine, any comparison sort must take at least $\Omega(n\log n)$ time.

Are they any problems where we have known lower bounds for the complexity of a problem when using non-deterministic machines?

$NP$-hard or -intermediate problems are probably the most interesting, but others would be interesting (for example, an $\Omega(n)$ lower bound on non-deterministic sorting).

Obviously, there are no known exponential lower-bounds for $NP$ problems, since that would imply $P\neq NP$, but are they any known polynomial bounds?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I'm pretty sure you have to write n numbers to sort n numbers, no matter how much magic your machine has access to. $\endgroup$
    – adrianN
    Jun 10, 2016 at 7:22
  • 2
    $\begingroup$ Are you sure that the first sentence is correct? First, I suspect you meant $\Omega(n \log n)$, not $O(n \log n)$. Second, there are sorting algorithms that are faster than that. The $\Omega(n \log n)$ lower bound is only for comparison-based sorting algorithms, but there are other sorting algorithms that don't fall in that model. $\endgroup$
    – D.W. ♦
    Jun 10, 2016 at 7:45
  • $\begingroup$ @D.W. my bad, changed to omega. $\endgroup$
    – jmite
    Jun 10, 2016 at 21:52

1 Answer 1

Reset to default
7
$\begingroup$

No. There are no known polynomial bounds. The best lower bounds known are merely linear.

As described here, the situation for circuits at least is "quite depressing": there are no known lower bounds that are better than $\sim 4n$. That's the case even when you pick the problem. There is no explicitly known problem where we can prove a lower bound better than $4n$.

Of course, for many problems it is easy to get a lower bound of $n$, by noting that for some functions it is necessary to read all of the input bits. So we can do only a constant factor better than the trivial lower bound.

Moreover, it is easy to prove (by a counting argument) that there exist functions that require at least $2^n/\text{poly}(n)$ gates to compute. The catch is that this proof is non-constructive: we don't know an explicit example of such a function. So there is an exponential gap between the best lower bound we know how to prove, and what we know must be the actual best lower bounds (even though we don't know how to prove it for any specific problem).

I don't expect anything fundamental to change if you replace circuits with RAM machine algorithms. Moreover, this shows that we don't know how to prove useful/non-trivial lower bounds for deterministic algorithms. Proving useful/non-trivial lower bounds for non-deterministic algorithms is even harder.

(The situation might be slightly different with Turing machines, as they're a bit slower/less powerful than RAM machine algorithms -- but you asked about the latter, so I assume we can ignore this.)

You might enjoy perusing the lower-bounds tag on CSTheory.SE.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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