A Problem on Time Complexity of Algorithms

169 Views Asked by At

I want no know if the following problem is solved or not, or how can I solve it?

Problem: For every integer $t$, Is there any problem that can be verified in $O(n^{s})$ but its solution can be found in $T(n)=\omega(n^{st})$, i.e., its solution can not be found in $O(n^{st})$.

By verifying, I mean that given a candidate solution $y$, we can judge whether $y$ is correct or not in time $O(n^s)$.

2

There are 2 best solutions below

4
On

I think what you want to know is covered by the answers to this question and this question on cstheory stackexchange.

It seems that the answer is likely to be yes, since it follows from $\mathbf{P} \neq \mathbf{NP}$ by a padding argument, but it isn't currently proven.

To elaborate, if I am understanding things correctly what you asking about is this statement:

For all $t$ and all $s$, there is a problem in $\mathbf{NTIME}(n^s)$ that is not in $\mathbf{TIME}(n^{s t})$.

There is a slight subtlety that you may be asking about search problems, but this is about decision problems, but I think that shouldn't matter.

According to the links, we don't even know that $\mathbf{NTIME}(n^s) \neq \mathbf{TIME}(n^s)$ so we couldn't even prove the weaker statement of finding a lower bounded of, say, $n^{s + 1}$, let alone a lower bound of $n ^{s t}$ (for $t>1$).

In other words, if we can't even manage to prove the much weaker statement that $\mathbf{NTIME}(n^s) \neq \mathbf{TIME}(n^s)$, we don't have much hope of proving the much harder statement that $\mathbf{NTIME}(n^s) \not \subseteq \mathbf{TIME}(n^{st})$. You can be fairly sure therefore that it is an open problem.

I also clamied that the statement follows from $\mathbf{P} \neq \mathbf{NP}$. To prove this, we shall assume that the statement fails and use it to prove $\mathbf{P} = \mathbf{NP}$.

If the statement is false, then in particular there is some $t$ and $s$ such that $\mathbf{NTIME}(n^s) \subseteq \mathbf{TIME}(n^{st})$. Let $f$ be a function that has a nonderministic algorithm that runs in polynomial time.

Let $p$ be a padding function, that concatenates the string $11\ldots110$ to its input so that $f(n)$ terminates in less than $|p(n)|$ steps. Then there is a linear time nondeterministic algorithm for $f'$ such that $f'(p(n)) = f(n)$ and $f'(m) = 0$ if there is no $n$ such that $m = p(n)$ (essentially the same algorithm as for $f$ but it is now linear time because the input is longer).

Since $f'(m) \in \mathbf{NTIME}(m)$ we know by assumption that $f'(m) \in \mathbf{TIME}(m^{st})$. So $f'$ has a deterministic algorithm that runs in polynomial time. By composing $f'$ with $p$, we also get a deterministic polynomial time algorithm for $f$, showing that $\mathbf{NP} \subseteq P$.

9
On

You have an array of $n^{st}$ integers and want to check if there is a zero. You check it in $O(1)$, if the index is given. You find it just by the brute-force search in $O(n^{st})$.