Inference and Resolution Questions and Answers

Answer: A

With thousands of rules and facts, testing every rule against every combination of facts after each change is prohibitive, and matching dominates the run time of such systems. Conflict resolution, which chooses among eligible rules, is the separate next step. Resolution pairing and unification are different operations. A step that appears to be bookkeeping and turns out to dominate the cost is worth identifying early, since optimising it is where the effort belongs.

Answer: B

A network such as Rete keeps the partial matches computed so far and updates them incrementally as facts are added or removed, so the work is proportional to the change rather than to the size of the base. The price is considerable memory. Rule ordering, compression and decision trees are different techniques. Trading memory for incremental rather than complete recomputation is a pattern that recurs wherever a system responds to a stream of small changes.

Answer: C

The procedure assigns a variable, propagates the consequences, and backtracks when a clause becomes empty, which is the basis of every modern satisfiability solver. Its two key inferences are unit propagation and the pure symbol rule. Conversion, resolution restriction and model enumeration are different activities. A sixty year old algorithm still at the heart of state of the art tools, after decades of refinement, is unusual and worth noticing. Reading the definition literally, rather than recalling a formula, is the reliable route through questions of this shape.

Answer: D

A clause reduced to a single unassigned literal forces that literal true, and doing so may reduce further clauses to units, cascading through the formula. It is by far the most important inference in a satisfiability solver and consumes most of its run time. Variable selection and clause deletion are different steps. An inference that is forced rather than chosen, and that cascades, is exactly what should be performed exhaustively before any search decision is made.

Answer: A

If a variable never appears negated, setting it true satisfies every clause containing it and can never hurt, so the assignment is safe without any search. It is a cheap inference that becomes rarer as the formula is reduced. The other options describe unrelated rules. An inference that is safe rather than merely plausible, and therefore requires no backtracking point, is worth applying whenever it is available.

Answer: B

When a conflict occurs, analysing the implication graph yields a clause capturing the cause, which is added permanently and prevents the same combination from being explored again. With restarts it transformed satisfiability solving from thousands to millions of variables. Variable ordering, exhaustive recording and preprocessing are different techniques. Converting a failure into a permanent constraint is the same idea as no-good learning in constraint solving, arrived at independently.

Answer: C

The learned clause records why the conflict occurred, so any future path recreating that cause, in any order, is cut immediately, whereas chronological backtracking would rediscover it repeatedly. Variable counts rise as clauses are added, the exclusion is far broader than one assignment, and no guarantee follows. Generalising from a specific failure to the condition responsible is what makes the learning worth its memory.

Answer: D

An unlucky early decision can trap the search for a very long time, and restarting with different heuristics while retaining the learned clauses escapes without losing progress. Clause deletion policies manage memory separately. Combined with learning, restarts turn a heavy tailed runtime into a manageable one. Two mechanisms that are modest alone and transformative together are worth remembering as a pair, since neither explains the improvement by itself.

Answer: A

Algorithms such as WalkSAT start from a random complete assignment and repeatedly flip a variable from an unsatisfied clause, mixing greedy and random choices. They solve very large satisfiable instances quickly and can never prove unsatisfiability. The other options describe unrelated procedures. The same division between complete systematic methods and incomplete local ones, with the same asymmetry about proving absence, appears here as in every other search setting.

Answer: B

Failing to find a satisfying assignment establishes only that none was found, since the method samples rather than enumerates. Systematic solvers with learning can exhaust the space and produce a refutation proof. Clause evaluation and initialisation are unaffected. Knowing what may be concluded from a negative result decides which family a task requiring a proof must use, and it is the same consideration that arises in constraint satisfaction. Working one numerical case through both cases side by side fixes the distinction better than any rule of thumb.