# Can we construct problems that can be solved in $\Theta(n^c)$ time, and tested in $O(n)$ time

CS sometimes seems take for granted that $\mathcal O(\text{poly}(n))$ is "easy", while $\mathcal O\left(2^{poly(n)}\right)$ is "difficult". I am interested in research into "difficult" polynomial-time algorithms, where the best-case solution to the constructed problem runs in $\Theta(n^c)$, where $c$ can be chosen to be large; but the solution could be tested in $O(n)$ time.

Question:

Given an integer $c$, can we construct problems that would:

• Take $\Theta\left(n^c\right)$ best-case-time to solve,
• While taking $\tilde{\mathcal O}(n)$ time, and $\tilde{\mathcal O}(n)$ space, to test a solution?

($\tilde{\mathcal O}(n)$ is soft-big-oh, meaning $O(n \log^k n)$ for some $k$)

Something I note - I might be mistaken somewhere here - is that presumably, if there is a $\mathcal O(n)$ algorithm to test the solution, then perhaps there can be a $\mathcal O(n)$ reduction to $\rm k\text{-}SAT$. If so, and, if $\rm P=NP$, and there was a polynomial-time algorithm, say ${\rm S{\small OLVE}}\left(\Phi(\mathbf x)\right) \in O({|\mathbf x|}^{\alpha})$ time, then I think this might contradict our $\Theta(n^c)$ problem, if $\alpha < c$.

The motivation would be to research the possibility of having a "one-way-function", that is linear(ithmic)-time computable, and best-case "difficult"-polynomial-time invert-able, where "difficult" means a high degree polynomial, instead of the usual exponential-time definition of "difficult"; perhaps this might be able to be used for cryptography even if $\rm P=NP$ (like "post-P-equals-NP-cryptography", similar to how there is a field of "post-quantum-cryptography").

• – Juho Nov 21 '13 at 14:55
• Your formal statement of the question is not quite right: a problem that takes $\Theta(n^c)$ to solve and $\log(n)$ time and space would fit, and that's a traditional hard problem with a weird way of expressing the input size. I guess you want soft-theta there. – Gilles 'SO- stop being evil' Nov 21 '13 at 15:40
• @Gilles I am not sure about the confusion, but did my edit clear it up? – Realz Slaw Nov 21 '13 at 16:12
• @Gilles Just to be clear, $\tilde{\mathcal O}(n)$ is essentially $\mathcal O(n)$, only after discarding logarithmic factors. So, I only wrote $\tilde{\mathcal O}(n)$ to give more leeway in the verification-time. For example, I allow $\mathcal O(n \log n)$ or $\mathcal O(n \log^2 n)$ verification time. – Realz Slaw Nov 21 '13 at 16:23
• you dont mention NP by name but this question is closely related. this tcs.se problem seems related best known deterministic time complexity lower bound for a problem in NP. also the question seems related to crypto, a possible answer to this problem would involve breaking PRNGs.... see also trapdoor functions – vzn Nov 21 '13 at 18:32

If you believe in the exponential time hypothesis, then you can construct such an example by padding SAT. The ETH states that solving SAT on $n$ variables takes time $2^{\Omega(n)}$; let's say the time is $T(n)$. We can assume that SAT instances consist of at most $O(n^3)$ clauses, and so have length at most $\tilde{O}(n^3)$. Pad such an instance by adding $N = T(n)^{1/c}$ (where $c > 1$ need not be an integer) spaces. According to the ETH, the resulting languages requires time $\Omega(n^c)$ to solve in the worst case (the "best case" time complexity of a problem is almost always $\tilde{O}(n)$, depending on your model of computation and how devious the problem is), but witnesses can be verified in time $\tilde{O}(n)$ and $O(\log n)$ space; most of these resources are spent on checking that the input is well-formed.

The same idea would work even with much weaker hypothesis, such as P$\neq$NP; I'll leave you the details.

• Very interesting. I find the question more interesting when allowing $\rm P=NP$ (though I did not state it explicitly), in the context of finding a polynomial sort of "hardness" that could be used for cryptography in the event that $\rm P=NP$. – Realz Slaw Dec 1 '13 at 20:16

if am understanding your question right, there are probably many examples of this based on "fixed parameters" of NP complete problems. eg finding a $k$-clique in a graph takes $O(n^{\sqrt k})$ time and can be verified in $O(n)$ time (a $k$ edge clique has $\sqrt k$ vertices).

• But there is no reason to believe a hard problem is only solvable by brute-force (in fact, we know this is not true for many NP-hard problems). – Juho Nov 21 '13 at 17:11
• J thats more an observation than an objection, the answer fits & rs is not asking for the optimal solution. but yes basically agreed; this all ties in closely with the P=?NP question (which in fact, as conjectured to be unequal, does in fact assert that there cannot be "much" difference between the optimal and brute force solutions). – vzn Nov 21 '13 at 17:21
• more strict answer. see rs is asking about $\Theta(n^c)$ which also implies $\Omega(n^c)$ ie a optimal lower bound. but there are almost no significant (nonlinear) lower bounds known for any algorithms except those constructed by diagonalization (time/space hierarchy thms).... – vzn Nov 21 '13 at 17:26
• You must always specify a model of computation whenever you consider lower bounds; but surely we have plenty of algorithms we know are optimal -- how about comparison based integer sorting algorithms for a starter? – Juho Nov 21 '13 at 17:31
• You (probably) can't verify cliques in time $O(n)$ on a Turing machine. (Though you can fix that by padding.) – Yuval Filmus Dec 10 '13 at 20:04