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).
Can we construct problems that can be solved in $\Theta(n^c)$ time, and tested in $O(n)$ time
algorithms;reference request;time complexity