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?


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

  • $\begingroup$ I already know all of the things you say in this answer, but I don't see how they respond to my question. One thing that might conceivably be confusing you is that I am using "nondeterministic" in the sense it is used in distributed computing; I certainly don't consider that if a problem can be solved in X time by a non-deterministic Turing machine then it can be solved in X time using a non-deterministic algorithm! Also, I wasn't identifying polynomial time with efficient; for large inputs in distributed computing, quadratic complexity would not be feasible. $\endgroup$
    – gmr
    Oct 29, 2014 at 1:50
  • $\begingroup$ "Canonical" just means that the algorithm as a whole is deterministic (though components of it may be non-deterministic): on the same input it will always produce the same solution, regardless of random delays that may affect the system. Sorry if I am using some wrong terminology here, please correct me! $\endgroup$
    – gmr
    Oct 29, 2014 at 1:53
  • $\begingroup$ Okay. Sorry about that. Specifically, you have randomness and non-determinism. These are two very separate things. Can you phrase your question in terms of those? $\endgroup$
    – Phylliida
    Oct 29, 2014 at 3:25
  • $\begingroup$ Non-determinism is talking about parallelism - specifically if we run many processors in parallel to get our answer. It is still deterministic in the sense that it always returns the same answer. Randomness, on the other hand, is talking about when you run an algorithm that has different answers each time, according to some probability distribution. Most random algorithms return the right result with high probability though, so they are just as many times as we need to get the right result with usually as high of a probability as we want. $\endgroup$
    – Phylliida
    Oct 29, 2014 at 3:26
  • $\begingroup$ Also, the reason we use polynomial time is because - almost always - once a polynomial time algorithm for a problem is found, we can optimize it by continuing to tweak it until it is fast enough for use in the industry. We also have things like average or worse runtime complexity so we can meaningfully discuss how, for example, many NP-Complete problems can be solved in polynomial time on average, but the best known algorithms still take exponential time on some instances. Or with other problems like factoring average-case complexity is also exponential as far as we know. $\endgroup$
    – Phylliida
    Oct 29, 2014 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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