A Constructive Generalization of the Borel-Cantelli Lemma with Application to the Complexity of Infinite Strings.

Abstract

A constructive adaptation of the Borel-Cantelli Lemma is obtained. Applications to several problems of complexity include the existence of hard 0,1 polynomials. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1975
Accession Number
ADA039869

Entities

People

  • Richard A. Demillo
  • Richard J. Lipton

Organizations

  • Yale University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Automata
  • Coefficients
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Information Systems
  • Numbers
  • Polynomials
  • Power Series
  • Probability
  • Real Numbers
  • Recursive Functions
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.