30
$\begingroup$

In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the degree of the polynomial run time is very large (e.g. $\Omega(n^{10000})$) such that any reasonably large problem is still out of reach for our current computing technology.

My question is: is it possible to find/construct a problem that have a lower-bound polynomial complexity $\Omega(n^p)$ to compute but an upper bound $O(n^q)$ to verify, with $q$ being quite small (e.g. $q=1$) and $p\gg q$. This problem would function essentially the same as current problems for which no known polynomial algorithms exist (e.g. factorization), and thus would still be usable in e.g. security systems in even in the case of $P=NP$.

$\endgroup$
32
$\begingroup$

No such problem is known (not with a known mathematical proof of a lower bound). Of course cryptographers would jump on it if we had one. As a result, cryptography is currently based on assumptions that we hope are true but we cannot prove (these are sometimes called "hardness assumptions"), and then we prove that if the assumption is valid, then the cryptographic scheme will be secure against attack.

Many good cryptosystems offer a reasonable candidate for a problem for which verification is much easier than solving, but we have no mathematical proof that this is necessarily so. For instance, factoring large integers seems like a good candidate for such a problem: it is easy to verify that you have correctly factored a large number, but it seems to be hard to find those factors in the first place. Breaking AES also seems like a good candidate for such a problem: it is easy for a cryptanalyst to verify that they have found the right AES key to decrypt some known plaintext pairs, but it seems to be hard to find the right AES key in the first place. However, we have no mathematical proof for any of these.

You might be shocked to learn that there is no explicitly known function family for which we can prove a super-linear lower bound (i.e., for every explicit function we can think of, we cannot rule out the possibility that it can be computed by a linear-size circuit). See here for a catalog of just how weak our known results are. This highlights just how far we are from being able to prove useful lower bounds.

I have some reading for you that might be helpful:

One early attempt at what you're hoping for are Merkle puzzles. These show a gap of the form you mention, with $O(n^2)$ time for attackers to break (i.e., to solve) but $O(n)$ time for defenders to compute (i.e., to verify). In your notation, this amounts to $p=2$ and $q=1$. This result holds only under the unproven assumption that solving a single puzzle takes $n$ steps of computation, but we have no concise (constant-length) puzzle for which we have a proof that solving will take that long, so even Merkle puzzles don't do what you are hoping for -- they still rely on an unproven assumption. And, there is a proof that the basic approach found in Merkle puzzles doesn't generalize to larger gaps (larger ratios of $p/q$), so they don't seem to lead somewhere that will be practically useful, even if we ignore that they rely on an unproven assumption like every other cryptosystem.

$\endgroup$
4
  • $\begingroup$ Is there a name for this issue? (i.e. for the issue of lacking a superlinear lower bound) It sounds like a pretty major fundamental CS problem. $\endgroup$
    – user541686
    Dec 27 '21 at 10:01
  • 1
    $\begingroup$ "For instance, we believe that to be true for factoring large integers, breaking RSA, ..." - Did you mean "making RSA possible"? Because factoring being hard allows RSA to be useful, it doesn't break it ;) "... breaking AES" - AES does not depend on number factorization, so I'm not sure why you're mentioning it in that context. $\endgroup$
    – marcelm
    Dec 27 '21 at 14:11
  • 1
    $\begingroup$ @marcelm, yes, that was intended as a list of at least three examples where we believe that to be true. I've edited my answer to try to explain more clearly. $\endgroup$
    – D.W.
    Dec 27 '21 at 23:59
  • 3
    $\begingroup$ @user541686, Well, it is the problem of proving lower bounds in complexity theory. It is closely related to the P vs NP problem. To prove that P != NP, it seems like we have to prove that some problem can't be solved in polynomial time. A natural warmup would be to try to find some problem where we can prove it can't be solved in linear time -- and we yet we don't even know how to do that warmup (for circuits as the model of computation), which shows just how far we are from knowing how to prove that P != NP. $\endgroup$
    – D.W.
    Dec 28 '21 at 0: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.