Automated decision making often requires solving difficult and primarily NP-hard problems. In many AI applications (e.g., planning, robotics, recommender systems), users can assist decision making by specifying their preferences over some domain of interest. To take preferences into account, we take a model-theoretic approach to both computations and preferences. Computational problems are characterized as model expansion, that is the logical task of expanding an input structure to satisfy a specification. The uniformity of the modeltheoretic approach allows us to link preferences and computations by introducing a framework of a prioritized model expansion. The main technical contribution is an analysis of the impact of preferences on the computational complexity of model expansion. We also discuss how prioritized model expansion can be related to other preference-based declarative programming paradigms. Finally, we study an application of our framework for the case where some information about preferences is missing.
Solving computationally hard problems (e.g., NP-hard) is in the core of many AI tasks.
Due to the significant progress in performance of modern solvers, finding solutions of
such problems (e.g., planning, travelling salesman, graph colouring, etc.) has become
feasible in many applications. Automated reasoning in intelligent systems often
generates a multitude of acceptable results. For example, in the context of resource
management, consider the prominent problem of Airport Gate Scheduling [
In many industrial applications, a decision maker may be inclined toward a subset of results. The preferred alternatives can be chosen in automated decision making. For instance, in the Airport Gate Scheduling problem, there could be some preferences for scheduling gates. A certain gate may be preferred to be assigned domestic flights rather than international flights. For language-independent solving, it is crucial to connect model expansion to a preference framework.
Since preferences play a key role in AI, a large number of frameworks for handling
preferences have been proposed during the last two decades such as [
In this paper, we propose a model-theoretic approach to handle preferences associated to a model expansion. The main motivation of our work is to connect model theory, descriptive complexity, and preference modelling to study computationally hard optimization problems. To the best our knowledge this is the first proposal of this kind in the literature. We aim to construct a language-independent preference framework that can be added to any declarative language (e.g., SAT, CSP, and ASP) which can be encoded as a model expansion. Toward this goal, we introduce the notion of a prioritized model expansion that extends model expansion by adding a set of preferences of a decision maker. Preferences can be expressed as priorities over ground atoms and then generalized to structures.
Using a model-theoretic approach has promising advantages from both modelling and
application viewpoints. For the modelling purposes, properties of model theory [
A model-theoretic view on modular systems with preferences was presented in [
Our main contributions are as follows. First, we propose the notion of prioritized model expansion that is a declarative framework for specifying computational problems with preferences. Second, we discuss that adding preference even in the simplest formulation leads to the rise of computational complexity of kP -complete (kth level in the polynomial hierarchy) model expansions. Third, we study the relations of some preferencebased frameworks with prioritized model expansion. We apply the computational complexity result of the task to obtain similar results for those frameworks. Fourth, a method to deal with incomplete information about preferences is proposed. Finally, we show that preservation theorems can be used for finding preferred solutions of problems with incomplete preferences. 2
A -structure A = (A; R1A; :::; RnA) is a tuple where = fR1; :::; Rng is a relational vocabulary that is a set of non-logical relation symbols Ri with associated arity ki, A is a domain, and for any Ri 2 , RiA is called the interpretation of Ri and RiA Aki . For a formula in any logic L, vocab( ) denotes the set of vocabulary symbols that appear in . A boolean query Q over -structures is defined as a mapping from the set of all -structures to f0,1g. A boolean query Q can be related to a model checking task such that for a formula ' in logic L and vocab(') = , Q'(A) = 1 if and only if A j= ' where A is a -structure.
Model expansion (MX) is the task of expanding a structure to satisfy a formula in any
logic L [
domain Dom, Find a structure A where A j= and expands I. (The decision version: is there a structure A such that A j= and A expands I?) We call A an expansion structure of MXI ; . Any expansion structure A is a structure with domain Dom.
For any logic L, the data complexity of (the decision version of) model expansion (MX)
is always in-between model checking (MC) and satisfiability (SAT). For example, for
first-order logic, MC is AC0, MX is NP-complete, SAT is undecidable. The combined
complexity of model expansion for first-order logic is NEXPTIME. A complexity
analysis of the three tasks (MC, MX, SAT) for several logics of interest was performed in
[
A variety of problems in AI such as the Airport Gate Scheduling problem can be reduced to graph colouring that is a widely discussed NP-hard problem. Graph colouring can be characterized as a first-order model expansion ( i.e, the problem specification is in first-order logic) as follows.
Example 1 Let binary relation E denotes edges relation between vertices and unary relation symbols R; G, and B denote red, green, and blue colours respectively. The formula specifies three-graph colouring
= 8x [(R(x) _ B(x) _ G(x)) ^:((R(x) ^ B(x)) _ (R(x) ^ G(x)) _ (B(x) ^ G(x)))] ^ 8x8y [E(x; y) (:(R(x) ^ R(y)) ^:(B(x) ^ B(y)) ^ :(G(x) ^ G(y)))]: A graph G = (V; E) is an instance structure with vocabulary = fEg and domain
(i.e., three-colouring of G) that interprets symbols R; B, and G satisfying . Note that
G (zV };|EG{; RA; BA; GA) j= : | {z }
A In order to study the computational aspect of prioritized model expansion, we employ the notion of a Turing machine as the model of computation.
decide whether some input string x in the oracle tape belongs to a language L. Let X be a complexity class.
Notation 1 P X is the class of languages (complexity class) that can be computed by a deterministic Turing machine with an oracle in X.
Notation 2 co-X is the complexity class of decision problems whose complements are in X.
The polynomial hierarchy (PH) that is a hierarchy of complexity classes is defined as P = 0P = 0P = 0P , kP+1 = NP kP , kP+1 = P kP , and kP+1 = coNP kP for k > 0. 3
In this section, we introduce the notion of prioritized model expansion which is model expansion with a collection of preferences of a decision maker. To model preferences, we define preference expression as an order over a set of ground atoms. We study the computational complexity of solving problems related to prioritized model expansions including Dominant Structure (i.e., given two structures, whether one is preferred to another), Optimal Expansion (i.e., given a structure, if it is an optimal expansion of a model expansion task), and Goal-Oriented Optimal Expansion (i.e., deciding if there is an optimal expansion satisfying a certain goal). At the end of this section, we define preference term as a generalization of preference expressions.
Preference Expression Let us fix a domain Dom. Consider k first order variables x1; :::; xk over Dom, vocabulary , and k-ary R 2 . A k-ary tuple a = (a1; :::; ak) is an assignment to an ordered set of variables x = (x1; :::; xk) such that for 1 i k, ai 2 Dom. We use the symbol a[xi] to denote value ai. R(a) is called a ground atom where a 2 Domk. A preference expression P is an order on a set of ground atoms.
Definition 3 (Preference Expression) A preference expression P is a pair P = (S ; wP ) where S is the set of all ground atoms of vocabulary over domain Dom and wP is a preorder on S .
For ground atoms R(a) and T (b) where R; T 2 , k-ary tuple a 2 Domk, and k0-ary tuple b 2 Domk0 , R(a) wP T (b) is read as R(a) is preferred to T (b). Also, R(a) is called strictly preferred to T (b) with notation R(a) AP T (b) if R(a) wP T (b) is true and T (b) wP R(a) does not hold. Also, R(a) P T (b) if R(a) wP T (b) and T (b) wP R(a).
Example 2 Consider a graph G = (V; E) and three colours R; B, and G as in Example 1. Suppose P = (S ; wP ) where domain V = fv1; v2; :::vng is a finite set of nodes, = fE; R; G; Bg, and R(v1) P R(v2) AP R(v3) states that it is equally preferred to have v1 and v2 with red colour and either of which is strictly preferred to v3 with red colour. Also, G(v2) A B(v3) denotes that having v2 with green colour is favoured to blue v3.
The relation between ground atoms can be lifted to a preference order among structures.
The idea of comparing two sets based on the preference on their members has been
widely discussed in different domains such as in database systems [
P B iff for all R; S 2 – Weak Pareto (WP). A and for all a 2 RA and all b 2 SB, R(a) wP S(b). – Upper Bound Dominance (UBD). A uPbd B iff for all S 2 and for all b 2 SB, for some R 2 , there is a such that a 2 RA and R(a) wP S(b). – Element Dominance (ED) A ePd B iff for some R; S 2 , there is b 2 SB and there is a 2 RA such that R(a) wP S(b) and there is not c for some T 2 such that c 2 T B and T (c) AP R(a).
To build a one-to-one correspondence between our preference model and other
preference frameworks in the literature, e.g., [
The problem of deciding if A is dominant is called Dominant Structure problem that is characterized as follows.
Definition 5 (Dominant Structure) Input: a preference expression P = (S ; wP ) and -structures A and B with domain
Proposition 1 Solving Dominant Structure problem is polynomial in the size of Dom. Proof. As stated by Definition 4, at most, we compare all tuples in RA and RB for all R 2 . The total possible number of k-ary tuples is jDomjk where k is the maximum arity of predicate symbols in . Therefore, O(jDomj2k) comparisons are required for each R 2 . Thus, deciding if A >P B is in m O(jDomj2k) (polynomial in the size of Dom) where m is the number of elements in .
We remark that the vocabulary is fixed and our discussion on computational complexity is focused on data complexity. 3.2
Prioritized Model Expansion A prioritized model expansion (PMX) is the problem of finding the most preferred expansion structures with respect to preferences.
Definition 6 (Prioritized Model Expansion)
expression P = (S ; wP ), Find structure A such that A is an expansion structure of
Notation 3 The problem of prioritized model expansion is denoted by I ; = (MXI ; ; P ) where MXI ; is a model expansion and P = (S ; wP ) is a preference expression.
I ; .
Definition 7 Any solution to a problem of prioritized model expansion an optimal expansion of
In the rest of this subsection, we study some decision problems that can be associated to a prioritized model expansion. The Optimal Expansion problem asks whether a given structure is an optimal expansion of a prioritized model expansion.
Definition 8 (Optimal Expansion)
= vocab( ) and P = (S ; wP ) is a preference expression.
= (MXI ; ; P ) where Proposition 2 Let model checking of (given a structure A, decide if A j= ) in MX co-NIP;Y .be in the complexity class Y . Solving the problem of Optimal Expansion is in Proof. The complementary problem is deciding if there is an expansion structure B such that B >P A. The complementary problem can be solved by a non-deterministic polynomial Turing machine guessing B with access to an oracle in Y that decides if B is an expansion of MXI ; (that includes checking if B expands I in polynomial time and if B j= in the complexity Y ) and based on Proposition 1, in polynomial time checks if B >P A. Thus, the complementary problem is in NPY and the original problem is in co-NPY .
One of the common tasks in many AI applications is to determine if a certain goal is
achieved by solutions of a problem, e.g., in planning [
Definition 9 (Goal-Oriented Optimal Expansion) Input: a prioritized model expansion I ; = (MXI ; ; P ) where P = (S ; wP ) is a preference expression, and a formula such that
= vocab( ) and is of the form i l.
Proposition 3 Let solving the Optimal Expansion problem of I ; = (MXI ; ; P ) be in the complexity class X. Solving the problem of Goal-Oriented Optimal Expansion is in NPX .
Proof. First, we non-deterministically guess a -structure A and in polynomial time check if ai 2 RiA, for 1 i l, that can be done by means of a non-deterministic polynomial Turing machine. Second, we check whether our guess is an optimal expansion that is in the complexity class X by the assumption. Thus, the problem can be solved by a non-deterministic polynomial Turing machine using an oracle in X. Hence, the problem is in NPX .
Goal-Oriented Optimal Expansion problem can be generalized to finding an optimal
expansion that satisfies a formula in a logic L . In this case, the complexity of model
checking in logic L (i.e., given a structure A if A j= ?) taken into account. However,
for the sake of simplicity, in this paper, we consider the goal as a conjunction of
ground atoms and it can be verified in polynomial time if a structure A satisfies .
It was discussed in [
is a first order formula. Therefore, when a decision version of a model expansion MXI ; is in kP , model checking of is in kP 1 and based on Proposition 2, solving Optimal Expansion (MXI ; ; P ) is in kP . The following result shows the impact of introducing preferences on Goal-Oriented Optimal Expansion for kP -complete model expansions.
Theorem 1 Let the decision version of a model expansion be lem of Goal-Oriented Expansion Structure is kP+1-complete. kP -complete. The probProof. The membership to kP+1 follows from the results of Proposition 2, Proposition 3, and properties of model expansion. Since the model expansion is in kP , the complexity of model checking of is in kP 1. Therefore, Pbased on proposition 2, the complexity of Optimal Expansion problem is in co-NP k 1 that is equal to kP .
P Also, based on Proposition 3, Goal-Oriented Optimal Expansion problem is in NP k
P or NP k that is equal to kP+1. For the proof of hardness, we consider the following steps.
First, we show that the problem of deciding the existence of minimal solutions of an
abductive logic program [
Second, consider an abductive logic program ALP = hH; M; Pi. Let us define a logic
program P0 as a set of rules of the form r : R(a) :S(b) for any R(a) wP S(b) such
that S(b) 2 H. Rule r indicates the less preferred ground atom (i.e., S(b)) belongs to
the set of hypothesis atoms H. Define P = P [ P0. The existence of a stable model
of a logic program is NP-complete and it can be translated into the decision version
of a model expansion as it was shown in [
Third, for model expansions in the higher levels of the polynomial hierarchy, consider
the following. kP -complete problems can be encoded as a combined logic program [
= (Pg; Pt) is called a combined logic program where Pg and Pt are logic programs over a set of propositional variables G and T respectively. M is a model of if it is a stable model of Pg and there is not a stable model N of Pt such that M \ G = N \ T . The decision version of this problem is 2P -complete. Recursively, the existence of a model of a combined program in depth 2 defined as 2 = (Pg2 ; (Pg1 ; Pt)) is 3P complete and similarly, in depth k, the existence of a model of (Pgk 1 ; k 2) is kP complete. We introduce abductive combined program as C = hH; M; i where = (Pg; Pt) is a combined logic program. W is a solution of C if there is a model S of (Pg [ W; Pt) such that M S. W is minimal if there is not a solution W 0 such that W 0 W .
Lemma 1 The problem of deciding if C = hH; M; ki for a given h 2 H has a minimal solution containing h is kP+1-complete.
Proof: The proof includes a translation from a quantified boolean formula (QBF) to C
for k = 2 and then by induction on k for k > 2, the result follows. Let ' be a boolean
formula in CNF and X = fx1; :::; xmg, W = fw1; :::; wmg, X0 = fx01; :::; x0mg,
Y = fy1; :::; yng, and Z = fz1; :::; zlg be a set of boolean variables in '. Let t, h, and f
be also boolean variables. Consider Pg as a set of rules of the form ft xi; x0ig, fwi
xig, fwi x0ig, ft y1; :::yn; hg, andff l1; :::; lrg where :(l1^; :::; ^lr) 2 '
similar to [
Finally, according to the previous steps and Lemma 1, finding a minimal solution of an abductive combined logic program in level k can be translated into a Goal-Oriented Optimal Expansion where the model expansion is kP -complete and hence the result follows.
Theorem 1 presents an important consequence of adding preferences to a kP -complete model expansion. For the problem of deciding if there is an expansion that satisfies a goal , adding preferences leads to a jump in the polynomial hierarchy. So, the preference relation between expansion structures derived from a preference expression can not be translated into axiomatization in polynomial time unless P=NP or the polynomial hierarchy collapses.
Example 3 Consider the problem of graph colouring that was described as model expansion in Example 1. Let G = (V; E) be the input graph where V = fv1; v2; v3; v4; v5g and EG = f(v1; v2); (v1; v3); (v2; v3); (v2; v4); (v4; v5); (v3; v5)g. Assume that we prefer red colour for v1. Also, v4 with red colour is favoured to v5 with red colour and blue v2 is preferred to green v2. These preference statements can be encoded by a preference expression P such that R(v1) AP B(v1) and R(v1) AP G(v1). Also, R(v4) AP R(v5) and B(v2) AP G(v2). The prioritized model expansion G; = (MXG; ; P ) where
3.3
Preference Term
In this subsection, we extend the notion of a preference expression by introducing
preference term that is an order on the domain of a first order variable. Preference terms
can be related to the concept of preferences in relational database systems. However,
unlike databases [
For a; b 2 A, a b means that a is preferred to b. Also, a b if a b and b a. Moreover, a b (a is strictly preferred to b) when a b and b a does not hold. Consider first order variables x1; :::; xk. The symbol dom(x) denotes the domain of x. Assume we are given k preference terms px1 = (dom(x1); 1); :::; pxk = (dom(xk); k ). A preference relation over k-ary tuples a and b is constructed from px1 ; :::; pxk as follows.
Definition 11 (Preference Relation on Tuples) Given a set of preference terms P = fpx1 ; :::; pxk g and two k-ary tuples a and b, we say that a is preferred to b with respect to P, notation a P b, iff for all pi 2 P, a[xi] i b[xi].
A preference expression P can be constructed from a set of preference terms P such that for a predicate symbol R, R(a) wP R(b) if and only if a P b. Prioritized model expansion then is extended to I ; = (MXI ; ; P) where P is derived from a set of preference terms and the semantics of optimal expansion is exactly as before. 4
In this section we study some examples of declarative specification of optimization problems that can be encoded as a prioritized model expansion and the associated computational complexity can be determined by the result of Theorem 1.
First, consider a prioritized logic program (PLP) [
I; = (MXI; ; P ) where I represents P r, characterizes the stable model semantics, and P is a preference expression representing c such that A is an optimal expansion of I; if and only if there is a preferred answer set M in that can be constructed in polynomial time from A. Deciding the existence of an optimal expansion of I; that satisfies a goal and a preferred answer set of PLP satisfying are
Proof. can be viewed as a preference expression in PMX and a program P r as a first
order model expansion. According to [
Second, an ASO program [
Theorem 3 Let ASO = (Pg; R) be an ASO program where Pg is disjunctive program and R is a set of preference rules. There is a prioritized model expansion I; = (MXI; ; P ) where specifies the stable model semantics and I represents Pg such that each optimal expansion A of I; can be mapped in polynomial time to a preferred answer set of ASO. The problem of deciding if there is an optimal expansion of I; that satisfies a goal or there is a solution of ASO satisfying is 3P -complete. Proof. An ASO program can be translated into a PLP (P r ; ) where P r is the union of Pg and a set of rules r1 and r2 where for each rule r 2 R of the form C1 > C2 body(r), we have r1 : n1 C1; body(r) and r2 : n2 C2; body(r) and n2 n1 is in . Therefore, based on Theorem 3, ASO can be converted into a prioritized model expansion. Since the existence of a an answer set that satisfies a set of ground atoms is 2P -complete ( i.e., brave reasoning in disjunctive logic programs with stable model semantics), deciding the existence of a solution of ASO that satisfies a goal formula is 3P -complete.
Finally, our proposal can be also connected to a variety of other preference frameworks
such as CP-nets [
In this section, we focus on handling incomplete preference statements associated to
search problems that are common in many practical cases. For example, assume that
for buying a car, the customer believes that the red colour is not the best option and it
is not the last choice either. In this example, some information is not known, that is to
determine what colour is better or worse than red. Dealing with missing information
is a broad field of study in database systems and declarative programming frameworks
[
We define valuation v(pixnc) as a function v : dom(x) [ ?! dom(x) that assigns elements in dom(x) to members of ? appearing in pixnc such that v(e) = e for any e 2 dom(x) and v(?i) 2 dom(x) for any ?i2?.
A preference term px = (dom(x); ) can be viewed as a first order structure with
vocabulary and domain dom(x). An incomplete preference term corresponds to the
well known notion of incomplete databases in which some fields value are null [
semJapnixtniccKs,=notva(tipoixnnc)JjpvixnicsKa, ivsadlueafitnioedn as. a set of preference terms as follows:
ifies properties of a car. A car dealership has a set of cars that is equivalent to an interpretation of car. Let fFord, Toyota, Hondag be the domain of model and fred, black, white, grayg be the domain of colour. Also, fuel can be gas, diesel, or electric. A set of preference terms are defined as follows. pm = (dom(m); m) where m denotes the model and Honda m Toyota m Ford, and pc = (dom(c); c) is an incomplete preference term over possible colours of a car where ?1 c red that means that red is not the best colour. Also, pf = (dom(f ); f ) where gas f diesel and gas f electric indicating the favorite cars are those using gas instead of electric power or diesel. For a valuation v where v(?1)=black, a black Honda with gas fuel is favoured to an electric red Ford.
Model expansion task can be coupled with incomplete preference terms as follows. Definition 14 Incomplete prioritized model expansion is denoted by a pair Iinc; = (MXI ; ; Pinc) where MXI ; is a model expansion and Pinc = fpixn1c; :::; pixnkcg is a set of incomplete preference terms.
The completion of an incomplete prioritized model expansion is defined as follows. tDicesfi(ndietnioonte1d5byThe Icinoc;mpK)leitsioanseotf of Ipinrci;or=itiz(eMd XmIod;el; ePxpinac)nsuinodnesrdcelfionseedd awsoJrldIinsce;mKan=(MXI ; ; JPincKJ) where JPincK = fJpixn1cK; :::; JpixnkcKg. oSptrtui mctaulreexApanissicoanlloefdaalln op0t2imJal Iienxc;paKn.sDioenteormfiniIinncg; if =agi(vMenXsItru;c;tuPreinci)s aifn Aoptiismaanl expansion of an incomplete prioritized model expansion is defined as follows.
domain Dom and an incomplete prioritized model expansion Iinc; = (MXI ; ; Pinc)
where = vocab( ) and Pinc = fpixn1c; :::; pixnkcg is a set of incomplete preference terms,
Question: Is A an optimal expansion of Iinc; ?
Recall that one of the advantages of using model-theoretic semantics is to utilize model
theory [
Let ?= f?1; :::; ?ng be a set of constants (nulls) and be a vocabulary of symbols. An
-structure C with domain Dom [ ? is called an incomplete structure. Each element of
? is a null value that represents a missing domain value. Given a first order sentence
and a structure C, the model checking task (query evaluation) is to decide whether C j=
. Naive model checking, according to [
the problem of Optimal Expansion of Incomplete prioritized model expansion is in coNPC.
Proof. In order to prove Theorem 4, it suffices to show that for two -structures A and B with domain Dom, A Pinc B can be decided in polynomial time in the size of Dom and the rest is only to follow the steps taken in the proof of Proposition 2. To this end, we take the following steps. First, we construct an incomplete structure called preference structure as follows. Let pixn1c = (dom(x1) [ ?; 1) be an incomplete preference term. We construct the following incomplete -structure C with domain Dom0 = Dom [ ? as follows. Consider vocabulary = fp1; SA; SBg and p1C = f(a1; a2)ja1; a2 2 Dom0 and a1 1 a2g. Also, SA = RA. Define SB1 = RB and SB2 = faj9b 2 SB1; a[x2; :::; xn] = b[x2; :::; xn] ^ a[x1] 2?g. Let define SB = SB1 [ SB2. Predicate p1 represents incomplete preferences among values of variable x1, SA is the set of all tuples in RA, and SB is the set of all tuples in RB plus all tuples in B whose value of x1 is replaced by a null.
Second, by slightly abuse of notation, valuation v(C) means valuation of any null value in C similar to the valuation of a preference term. Valuation v is a strong onto homomorphism ( v is a surjective function) from C to C0 where dom(C) = Dom [ ? and dom(C0) = Dom. The symbol JCK denotes the set of all C0 where there is a valuation v (strong onto homomorphism) such that v(C) = C0. Any C0 2 JCK is called a completion of C under closed world semantics.
Third, according to Definition 4, Definition 10, and Definition 11, the task of deciding if
B is preferred to A can be reduced to evaluation of whether C j= 8x18x(SA(x1; x)) !
9y1y(SB)(y1; y) ^ p1(y1; x1)) where x = (x2; :::xn) and y = (y2; :::; yn). It was
discussed in [
B For a set of incomplete preference terms Pinc = fpixn1c; :::; pixnkcg, by induction on the number of incomplete preference terms, deciding B Pinc A is polynomial in the size of Dom. The immediate result similar to Proposition 1 is that for a model expansion MXI; with model checking of in the complexity C, deciding if a given structure is a preferred expansion based on a set of incomplete preference terms is in co-NPC. The following result immediately follows from Theorem 4.
Corollary 1 Let solving the decision version of model expansion MXI ; be kp-complete. Solving the problem of Goal-Oriented Optimal Expansion with incomplete prioritized model expansion is kp+1-complete.
We proposed a novel language-independent preference framework and connected it to model expansion for characterizing preference-based computational decision and search problems. We demonstrated that adding preferences raises the computational complexity of deciding the existence of an expansion structure satisfying a goal. Additionally, we introduced a new method to model incomplete preferences and used model theory results, namely preservation theorems, to find preferred expansions more efficiently. In future work, we will devise an algorithm that solves prioritized model expansion using generic solvers empowered by propagators. The solver would provide symbolic explanations for rejecting and accepting models, and would follow a preferred computation path to prune the search space.