(21th-April-2020)
10 binary features can describe 2power10=1,024 states.
20 binary features can describe 2power20=1,048,576 states.
30 binary features can describe 2power30=1,073,741,824 states.
100 binary features can describe 2power100=1,267,650,600,228,229,401,496,703,205,376 states.
Reasoning in terms of thirty features may be easier than reasoning in terms of more than a billion states. One hundred features is not that many, but reasoning in terms of more than 2power100 states explicitly is not possible. Many problems have thousands if not millions of features.
Typically the features are not independent, in that there may be constraints on the values of different features. One problem is to determine what states are possible given the features and the constraints.
Possible Worlds, Variables, and Constraints
To keep the formalism simple and general, we develop the notion of features without considering time explicitly. Constraint satisfaction problems will be described in terms of possible worlds.
When we are not modeling change, there is a direct one-to-one correspondence between features and variables, and between states and possible worlds. A possible world is a possible way the world (the real world or some imaginary world) could be. For example, when representing a crossword puzzle, the possible worlds correspond to the ways the crossword could be filled out. In the electrical environment, a possible world specifies the position of every switch and the status of every component.
Possible worlds are described by algebraic variables. An algebraic variable is a symbol used to denote features of possible worlds. Algebraic variables will be written starting with an upper-case letter. Each algebraic variable V has an associated domain, dom(V), which is the set of values the variable can take on.
Comments