Accession Number:

ADA171505

Title:

Nonsequential Computation and Laws of Nature.

Descriptive Note:

Interim rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

• Vitanyi,Paul M.

Report Date:

1986-05-01

Pagination or Media Count:

22.0

Abstract:

Traditionally, computational complexity theory deals with sequential computations. In the computational models the underlying physics is hardly accounted for. This attitude has persisted in common models for parallel computations. Wrongly, as we shall argue, since the laws of physics intrude forcefully when we want to obtain realistic estimates of the performance of parallel or distributed algorithms. First, we shall explain why it is reasonable to abstract away from the physical details in sequential computations. Second, we show why certain common approaches in the theory of parallel complexity do not give useful information about the actual complexity of the parallel computation. Third, we give some examples of the interplay between physical considerations and actual complexity of distributed computations. author

Descriptors:

• *COMPUTATIONS
• *PARALLEL PROCESSING
• ALGORITHMS
• WIRE
• ESTIMATES
• TIME
• TREES
• PHYSICS

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE