---
title: "On the Space-Time Trade-off in Solving Constraint Satisfaction Problems"
authors:
  - "Roberto J. Bayardo Jr."
  - "Daniel P. Miranker"
doi: ""
url: "https://ijcai.org/proceedings/1995/73"
pdf: "https://ijcai.org/proceedings/1995/0073.pdf"
venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence"
year: 1995
pages: "558-561"
track: "Constraint Satisfaction"
keywords:
---

# On the Space-Time Trade-off in Solving Constraint Satisfaction Problems

Roberto J. Bayardo Jr., Daniel P. Miranker

*Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 558-561.

## Abstract

A common technique for bounding the runtime required to solve a constraint satisfaction problem is to exploit the structure of the problem's constraint graph [Dechter, 92]. We show that a simple structure-based technique with a minimal space requirement, pseudo-tree search [Freuder & Quinn, 85], is capable of bounding runtime almost as effectively as the best exponential space-consuming schemes. Specifically, if we let n denote the number of variables in the problem, w* denote the exponent in the complexity function of the best structure-based techniques, and h denote the exponent from pseudotree search, we show h ~ (w* +I) (lg(n) + 1) . The result should allow reductions in the amount of real-time accessible memory required for predicting runtime when solving CSP equivalent problems.