# Complexity of Problems and Ease of Verification

Comparison-based sorting algorithms have a minimum worst-case complexity of $$O(n \log n)$$, while it is easy to check that an array is sorted in $$O(n)$$ time.

Are there other problems with proven minimum complexity $$O(n^k)$$ for some $$k > 1$$ that can be checked in $$O(n)$$ time? How high can $$k$$ get?

• "Are there other problems with proven minimum complexity $O(n^k)$ for some $k > 1$ that can be checked in $O(n)$ time?" What do you mean, any other problems? $O(n \log n)$ is strictly less than $O(n^k)$ for any $k > 1$. Your comparison-based sorting example is not a proper example for your question. – orlp Oct 1 '18 at 13:29

## 1 Answer

Trivial arbitrarily hard example based on the existence of an one-way function $$f : \mathbb{N}^k \to \{0, 1\}$$. The problem:

Given a set $$S$$ of size $$n$$, can we choose a tuple $$t$$ formed from $$k$$ elements of $$S$$ such that $$f(t) = 1$$?

Since $$f$$ is one-way you must check all $$n^k$$ possible $$k$$-tuplets of elements from $$S$$, but checking whether a proposed solution is correct is simply $$O(1)$$ time.

However, if you're looking for interesting or deep results, I'm afraid you're out of luck. Forget "at least this hard to compute but easy to verify", we barely even have "at least this hard to compute" for almost anything. See this scarce list here.

Why are lower bounds so scarce? Because they essentially require omniscience in a certain subject area. You must prove that no matter how smart, doing better than the lower bound is impossible. It's as if you're simultaneously exploring every possible algorithm, finding their time complexities and showing that they're bigger than the lower bound. It's nearly impossible, which is why we barely have any proofs that go beyond some version of "you must read all input".