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$

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.

| cite | improve this answer | |
$\endgroup$

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.