Can the use of negation speed-up parallel computation, let alone of natural computational problems?
A dramatic affirmative answer was provided by a WIS scientist and his collaborator. Referring to the problem of finding a large matching in a given graph, they showed that parallel computations that do not use negation use exponentially more time than parallel computations that use negation.