Simulations and Reductions
Abstract
In complexity theory, it is common to prove results by reduction from one problem to another. For example, textbooks typically prove from first principles that satisfiability (SAT) is NP complete. To show that another problem is also NP-complete, it is enough to show that SAT (or some other problem known to be NP-complete) reduces to the problem in question. Reductions are appealing because they are often technically simpler than proving NP completeness directly.
Reductions can also be applied in distributed computing. This chapter describes a general technique for showing that a protocol in one model can be transformed into a protocol in another model. In addition, we describe a specific transformation, ...
Get Distributed Computing Through Combinatorial Topology now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
