The primary contribution of this paper consists in using the
paradigm [1,2] to define the new concept of
of a constraint network. The well known parameter
is graph based, and cannot capture context sensitive information. This often results in a very loose upper bound on the actual complexity of the problem. A typical example is the compact result of a compilation schemes such as
ordered binary decision diagram
(OBDD), in spite of a large tree-width (and path-width). The semantic width is based on the notion of equivalent constraint networks. The idea is to capture the intrinsic hardness of a problem by the smallest width equivalent network.