1
$\begingroup$

What would be the practical consequences of ZPP=exptime. It would be pretty ridiculous if the was true but what if it was?

$\endgroup$
1
$\begingroup$

If ZPP = EXPTIME then NP $\subseteq$ ZPP, which implies NP $\subseteq$ BPP. As described in Russell Impagliazzo's informal paper "A personal view of average-case complexity", we would be living in a world he calls Algorithmica.

Algorithmica is the world in which $P = NP$ or some moral equivalent, e.g. $NP \subseteq BPP$. [...]

Such a method of automatically producing a solution for a problem from the method of recognizing a valid solution would revolutionize computer science. Seemingly intractable algorithmic problems would become trivial. Almost any type of optimization problem would be easy and automatic; for example, VLSI design would no longer use heuristics, but could instead produce exactly optimal layouts for problems once a criterion for optimality was given. Programming languages would not need to involve instructions on how the computation should be performed. Instead, one would just specify the properties that a desired output should have in relation to the input.

And so on. Read the paper for more extrapolation on this topic, along with the consequences of less fantastic algorithmic complexity conjectures being true. And observe @Dmitry's caveat: Knowing a problem is in a tractable complexity class isn't the same as having an efficient algorithm for the problem that takes advantage of that fact.

Theoretically, ZPP = EXPTIME implies EXPTIME $\subseteq$ BPP. Since we already know P $\subset$ EXPTIME we have P $\subset$ BPP as well, which means there are some polynomial-time randomized algorithms that cannot be derandomized. This is another way of saying that pseudo-random number generators will never be as effective as true randomness, algorithmically, which would be a very interesting result.

We know that BPP is low for itself, i.e. BPP$^{BPP}$ = BPP. Therefore an EXPTIME no more powerful than BPP must be low for itself as well, which removes the separation between some exponential classes, e.g. EXPTIME = EEXP = EE = EEE. This in turn makes some decidable but intractable problems simply decidable. For example, deciding the truth of first-order mathematical statements expressed in Presburger arithmetic would now be in BPP.

We also know that BPP $\subseteq \Sigma^P_2 \cap \Pi^P_2$. Together with EXPTIME $\subseteq$ BPP this means that the polynomial hierarchy collapses to the second level; the oracle calls above that level do not offer any more computational power, as EXPTIME is powerful enough to capture all the rest of PH. Since P is strictly a subset of BPP and P = NP would collapse PH completely, bringing P and BPP together, ZPP = EXPTIME would imply P $\neq$ NP. Interestingly, I think NP = co-NP would still be an open problem. But with the proof writing power you'd get from EXPTIME being tractable, I doubt the problem would be open for long.

$\endgroup$
1
  • $\begingroup$ I think they are still talking about theoretical consequences, not practical ones. Practical consequences, similarly to "what happens if $P=NP$", will be along the lines "in all likelihood, nothing will change (unless we also design practically efficient algorithms)". So it'll revolutionize computer science, but won't change the world we live in. $\endgroup$
    – user114966
    Apr 4 at 1:38

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.