We introduce a parameter that measures the 'constrainedness' of an ensemble of combinatorial problems. If problems are over-constrained, they are likely to be insoluble. If problems are under-constrained, they are likely to be soluble. This constrainedness parameter generalizes a number of parameters previously used in different NP-complete problem classes. Phase transitions in different NP classes can thus be directly compared. This parameter can also be used as a heuristic to guide search. It captures the intuition of making the most constrained choice first, since it is often useful to branch into the least constrained sub-problem. Many widely disparate heuristics can be seen as minimizing contrainedness
The Constrainedness of Search
1996-01-01
Abstract
We introduce a parameter that measures the 'constrainedness' of an ensemble of combinatorial problems. If problems are over-constrained, they are likely to be insoluble. If problems are under-constrained, they are likely to be soluble. This constrainedness parameter generalizes a number of parameters previously used in different NP-complete problem classes. Phase transitions in different NP classes can thus be directly compared. This parameter can also be used as a heuristic to guide search. It captures the intuition of making the most constrained choice first, since it is often useful to branch into the least constrained sub-problem. Many widely disparate heuristics can be seen as minimizing contrainednessI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
