An Introduction to Boolean Function Complexity.

Abstract

The complexity of a finite Boolean function may be defined with respect to its computation by networks of logical elements in a variety of ways. The three complexities of circuit size, formula size and depth are considered, and some of the principal results concerning their relationships and estimations are presented, with outlined proofs for some of ths simpler theorems. This survey is restricted to networks in which all two-argument logical functions may be used.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1976
Accession Number
ADA032122

Entities

People

  • Michael S. Paterson

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Automata
  • Automata Theory
  • Circuits
  • Computational Complexity
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Digital Computers
  • Electronic Equipment
  • Information Theory
  • Language
  • Machines
  • Mathematics
  • Theorems
  • Theoretical Computer Science
  • Trees (Data Structures)

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Theoretical Analysis.