Computational Limitations on Learning from Examples

Leonard Pitt, Leslie G. Valiant

Research output: Contribution to journalArticlepeer-review


The computational complexity of learning Boolean concepts from examples is investigated. It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP. These classes include (a) disjunctions of two monomials, (b) Boolean threshold functions, and (c) Boolean formulas in which each variable occurs at most once. Relationships between learning of heuristics and finding approximate solutions to NP-hard optimization problems are given.

Original languageEnglish (US)
Pages (from-to)965-984
Number of pages20
JournalJournal of the ACM (JACM)
Issue number4
StatePublished - Oct 1 1988
Externally publishedYes


  • Distribution-free learning
  • NPcompleteness
  • inductive inference
  • learnability

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'Computational Limitations on Learning from Examples'. Together they form a unique fingerprint.

Cite this