Inference and Resolution Questions and Answers

Answer: C

Techniques such as variable elimination, subsumption and self subsuming resolution often shrink an industrial formula substantially before any search occurs. Parsing, ordering and configuration are separate activities, though all happen before the search. Spending effort on simplifying a problem before attacking it, rather than beginning immediately, is a habit that pays in almost every combinatorial setting.

Answer: D

Resolving every clause containing a variable positively against every one containing it negatively removes the variable, and the exchange is worthwhile when the resolvents number fewer than the originals. Unused variables are trivially removable, assignment is search, and renaming is bookkeeping. A transformation applied only when a measurable criterion says it will help, rather than universally, is what makes preprocessing a net gain.

Answer: A

Eliminating a variable appearing in many clauses of both polarities produces a quadratic number of resolvents, so the operation is attempted only where a size criterion is met. Satisfiability is preserved, termination is manageable, and search proceeds normally afterwards. Applying a transformation under a cost benefit test, rather than because it is available, is the difference between a preprocessing phase that helps and one that hurts.

Answer: B

Systematic search with propagation can exhaust the space and prove no solution exists, while local search samples and can only succeed or give up. Incomplete methods are generally sound: what they find is genuinely a solution. Speed varies by instance and completeness is quite distinct from soundness. Classifying a method by what may be concluded from its failure, rather than by its success rate, is what decides whether it suits a verification task.

Answer: C

Only a method that exhausts the space, or derives a contradiction, can assert absence, and the incomplete methods can never do so however long they run. That is not a matter of time. The stochastic methods sample and cannot exhaust. Knowing which family a task requires, before selecting an algorithm within it, is a decision that follows directly from what must be concluded at the end.

Answer: D

If a negative result must be trusted, only a complete method will serve, whereas if any solution will do and none may exist harmlessly, an incomplete method is often far faster. Prior experience, time and libraries are practical considerations that follow. Asking what the output will be used for, before choosing how to compute it, is the same discipline the agent framework applies to performance measures.

Answer: A

Each learned clause is derived by resolutions along the implication graph, so a solver's run traces out a resolution refutation which it can emit and have checked. Resolution applies to both logics, and the two traditions inform each other continually. Recognising that a highly engineered modern tool is performing a classical inference rule under the surface connects two literatures that are often taught as unrelated.

Answer: B

Since a conflict driven solver produces a resolution proof, lower bounds on the length of resolution proofs for a family of formulas bound how quickly any such solver can decide them. Certain pigeonhole formulas require exponentially long resolution proofs and defeat every such solver accordingly. Replacement, first order use and polynomial termination do not follow. Theory bounding what engineering can achieve, rather than merely describing it, is an unusually useful kind of result.

Answer: C

The statement that n plus one objects cannot fit into n boxes is easy for a person and provably hard for resolution, requiring exponentially many steps. Solvers based on resolution therefore fail on them at modest sizes, and stronger proof systems are needed. Normal form, soundness and decidability are unaffected. A family of formulas that separates human reasoning from a particular proof system is instructive about the limits of that system rather than about difficulty in general.

Answer: D

A lower bound on proof length applies however cleverly the search is directed, so it bounds the whole family of algorithms based on that system. Stronger systems may have short proofs of the same formulas. Soundness and universal hardness do not follow. A result that rules out an entire class of approaches, rather than a particular implementation, is worth knowing before effort is spent optimising within that class.