---
title: "A Problem Reduction Model for Non-Independent Subproblems"
authors:
  - "Giorgio Levi"
  - "Franco Sirovich"
doi: ""
url: "https://ijcai.org/proceedings/1975/52"
pdf: "https://ijcai.org/proceedings/1975/0052.pdf"
venue: "Proceedings of the Fourth International Joint Conference on Artificial Intelligence"
year: 1975
pages: "340-343"
track: "Search Techniques"
keywords:
---

# A Problem Reduction Model for Non-Independent Subproblems

Giorgio Levi, Franco Sirovich

*Proceedings of the Fourth International Joint Conference on Artificial Intelligence*, pages 340-343.

## Abstract

A hypergraph model is introduced, which besides including the AND/OR graph and state space graph models as particulars, is adequate for problem solving tasks involving non independent subproblems. The hypergraph model is shown to be grounded on a nonstandard notion of conjunction such that the truth of a conjunction does not necessarily imply the truth of the conjuncts. A hypergraph search algorithm is given and shown to be equivalent to a resolution-based theorem prowr in a first order logic augmented with the special conjunction. A characterization is given of the class of problems requiring the full descriptive power of our model. The class includes problems involving resources, plan formation, simplification of predicate logic programs.