---
title: "Learning Disjunction of Conjunctions"
authors:
  - "Leslie G. Valiant"
doi: ""
url: "https://ijcai.org/proceedings/1985/107"
pdf: "https://ijcai.org/proceedings/1985/0107.pdf"
venue: "Proceedings of the Ninth International Joint Conference on Artificial Intelligence"
year: 1985
pages: "560-565"
track: "Learning and Acquisition"
keywords:
---

# Learning Disjunction of Conjunctions

Leslie G. Valiant

*Proceedings of the Ninth International Joint Conference on Artificial Intelligence*, pages 560-565.

## Abstract

The question of wheth e r concepts expressible as disjun ctio ns of conjunctions can be learn e d from examples in polynomial time is investigated . Positive results are shown for significant subclasses that allow not only propositional predicates but also some relations . The algorithms are extend e d so as to be provably tolerant to a certain quantifiable error rate in the examples data . It is further shown that under certain restrictions on these subclasses th e l ear ning algorithms ar e well suited to implementation on neural networks of threshold elements. The possible importance of disjunctions of conjunctions as a knowledge repr ese ntation stems from th e observations that on the one hand humans appear t o like using it , and , on the other, that there is circumstantial evidence that significantly larger classes may not be learnable in polynomial time . An NP-completeness result corroborating the latter is also presented.