Inference and Resolution Questions and Answers

Answer: C

Random three literal formulas are almost always satisfiable below about four point two clauses per variable and almost always unsatisfiable above it, with the hard instances concentrated at the boundary. Far from the ratio the answer is easy either way. The other options describe unrelated changes. That difficulty depends on a single structural ratio, and peaks where the answer is genuinely in doubt, is both a useful benchmarking fact and an appealing piece of science.

Answer: D

With few clauses almost any assignment works and local search finds one immediately, while with very many the contradiction is shallow and propagation reveals it quickly. Only near the boundary is the answer genuinely uncertain and the search long. Variable counts, tuning and simplification are not the reason. That difficulty is greatest where the answer is least predictable is intuitive once stated and it generalises well beyond satisfiability. Naming the cost of a choice alongside its benefit is what turns a fact into a design decision.

Answer: A

Refutation converts an entailment question into a satisfiability question, which is what resolution and every satisfiability based prover exploit. Direct derivation is possible in other proof systems but resolution is only refutation complete. Counter-models and rhetorical refutation are different notions. Adopting a proof strategy because it suits the available machinery, rather than because it is the most natural, is a recurring practical compromise. Checking the units of each quantity catches a wrong formula before the arithmetic begins.

Answer: B

The mathematical technique and machine refutation are the same idea: assume the opposite and show that something impossible follows. Recognising the correspondence makes the prover's strategy familiar rather than strange. Direct contradiction between premises, contraposition and non-constructive arguments are related but distinct. A machine procedure that turns out to formalise a technique already familiar from mathematics is easier to trust and easier to debug.

Answer: C

Each propagated assignment is recorded with the clause that forced it, and when a conflict arises the graph is analysed backwards to find the decisions responsible. That analysis produces the learned clause. Formula structure and resolution graphs are different objects. Keeping a record of why each step was taken, so that a failure can be diagnosed rather than merely detected, is the same principle as a truth maintenance system's justifications. A limit that survives making every external component ideal is an intrinsic one, and worth knowing for that reason.

Answer: D

The search alternates between forced assignments, which need no backtracking point, and chosen ones, which do, and only the decisions form the backtracking structure. Frequency, criticality and pure symbols are different notions, though the pure symbol rule also gives a forced assignment. Separating what is inferred from what is guessed is what makes the backtracking structure minimal and the conflict analysis meaningful.

Answer: A

Activity based heuristics score variables by how often they appear in recent conflict analyses and decay the scores over time, which focuses the search on the currently difficult part of the problem. Textual order performs poorly, domains are boolean, and pure randomness wastes the information conflicts provide. Letting the search's own history direct its next choice is a form of learning within a single run and it is one of the reasons modern solvers perform as they do.

Answer: B

Such a prover repeatedly resolves and simplifies until either the empty clause appears or no new clause can be derived, the second outcome proving satisfiability for decidable fragments. Redundancy elimination is essential to keep it finite. The other options misread the term. A procedure whose termination without success is itself informative, in the fragments where it terminates, is more useful than one that simply runs out of time. Reading the definition literally, rather than recalling a formula, is the reliable route through questions of this shape.

Answer: C

Maintaining a passive set and an active set, and repeatedly moving one clause from passive to active while resolving it against everything active, gives a fair and efficient organisation. Which clause is chosen is where heuristics enter. Exhaustive pairing is what the organisation avoids, and random or strictly chronological choice performs poorly. An algorithmic skeleton that separates what must be done from the heuristic choice of order is what allows the heuristics to be varied independently.

Answer: D

A heuristic that always prefers short clauses might postpone a long one indefinitely, losing completeness, so a fairness mechanism such as alternating with age is required. Memory, ordering and subsumption are separate concerns. That an aggressive heuristic can destroy completeness unless deliberately tempered is a lesson that applies to any priority driven search, and the remedy is always some form of guaranteed eventual selection.