What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?

Question

For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it is fundamentally easier to compute a solution to such a problem than to compute a canonical solution. Some non-deterministic algorithm would outperform every deterministic algorithm. However, it is likely that randomness does not buy much. Parallelism, on the other hand, certainly does improve the running time of algorithms. In general, if we have lots of processors but communication is expensive and synchronization is infeasible, we might expect non-deterministic algorithms to outperform deterministic ones. However, in many cases it seems possible to convert non-deterministic algorithms into deterministic ones under reasonable assumptions. For instance, one way to look for a satisfying assignment is to divide up the search space between multiple processors and then return the first solution that comes back. That's non-deterministic, but it can easily be made deterministic by putting an appropriate order on the solution space and then waiting after receiving the first solution until one can be sure that no smaller solution exists. Are there some natural examples of problems where such a conversion does not work? I.e., problems that we can expect to solve efficiently using parallelism but where we cannot expect to find canonical solutions using parallelism?

Answer 1

I think you're mixing up parallelism with non-determinism. The thing about parallelism is that any problem that can be solved in polynomial time using a polynomial number of processors can be also be solved in polynomial time using a single processor, simply by simulating each processor's work one at a time.

NC is the class of problems that can be sped up through parallelism using a polynomial number of processors, and whether or not $NC=P$ is an open problem (whether or not all problems that can be solved in polynomial time can be sped up through parallelism). We know that NC is within P because of the previous paragraph, however if you're looking for problems that probably can't be sped up through parallelism (I think this is what you're asking for?), see P-Complete problems - these can't be sped up through parallelism unless $NC=P$.

On the other hand, non-determinism is talking about more generally what happens if we run all paths in parallel and return "yes" if at least one parallel processor found an answer that works. For NP-Complete problems, we're pretty sure that this requires an exponential number of processors to solve them in polynomial time, and an exponential amount of time to solve sequentially ("canonically"?) as well. In the example of subset sum (a known NP-Complete problem), you'd run one processor for each subset, and if any processors find a sum of 0 it would return it and you'd return yes, otherwise if none do you'd return no.

Whether non-determinism helps us or not in problems that can be verified in polynomial time is the problem of whether or not $P=NP$, and we're almost certain $P\neq NP$, it's just not proved yet so we're not 100% sure. Still there's many lesser assumptions that we're also pretty sure are true that would have to be broken first (for example collapse of the polynomial hierarchy, non-existence of one way functions/cryptography/pseudorandom generators).

Whether or not $NEXPTIME=EXPTIME$ is the exponential equivalent of this question, and by a padding argument we know that if $P=NP$, $NEXPTIME=EXPTIME$.

Finally, you mentioned that "it is likely that randomness doesn't buy much." Formally BPP is the class of problems that can be solved efficiently with a randomized algorithm, and you're right that we suspect $BPP=P$, but that's also something we haven't yet formally proved. Also see this and this question.