6
$\begingroup$

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").

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ Decision problems in P without fast algorithms and Polynomial-time algorithms with huge exponent/constant seem relevant. $\endgroup$ – Juho Nov 21 '13 at 14:55
  • $\begingroup$ 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. $\endgroup$ – Gilles 'SO- stop being evil' Nov 21 '13 at 15:40
  • $\begingroup$ @Gilles I am not sure about the confusion, but did my edit clear it up? $\endgroup$ – Realz Slaw Nov 21 '13 at 16:12
  • $\begingroup$ @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. $\endgroup$ – Realz Slaw Nov 21 '13 at 16:23
  • 1
    $\begingroup$ 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 $\endgroup$ – vzn Nov 21 '13 at 18:32
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Realz Slaw Dec 1 '13 at 20:16
1
$\begingroup$

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).

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Juho Nov 21 '13 at 17:11
  • $\begingroup$ 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). $\endgroup$ – vzn Nov 21 '13 at 17:21
  • 1
    $\begingroup$ 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).... $\endgroup$ – vzn Nov 21 '13 at 17:26
  • 1
    $\begingroup$ 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? $\endgroup$ – Juho Nov 21 '13 at 17:31
  • 1
    $\begingroup$ You (probably) can't verify cliques in time $O(n)$ on a Turing machine. (Though you can fix that by padding.) $\endgroup$ – Yuval Filmus Dec 10 '13 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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