Nonsequential Computation and Laws of Nature.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1986
Accession Number
ADA171505

Entities

People

  • Paul M. Vitanyi

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Advanced Electronics
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Aspect Ratio
  • Central Processing Units
  • Computational Complexity
  • Computations
  • Computer Networks
  • Computer Science
  • Computers
  • Computing Devices
  • Differential Equations
  • Electrical Engineering
  • Equations
  • Information Processing
  • Logic
  • Nonsequential
  • Parallel Computing
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Educational Psychology
  • Quantum spin resonance or Electron Paramagnetic Resonance spectroscopy.