Inference and Resolution Questions and Answers

Q: Why does watching two literals suffice?

So long as two literals remain unassigned the clause is neither unit nor conflicting, so it need not be examined, and only when a watch is falsified must a replacement be sought. Determining truth requires all the literals, clause lengths vary widely, and the watches move during the search. An invariant that guarantees a data structure need not be consulted is exactly what makes lazy updating correct as well as fast.

Q: How is the assignment trail of a solver organised?

Each chosen assignment opens a new level, and everything propagated from it belongs to that level, so backjumping means returning to a specified earlier level. Conflict analysis computes which level to return to. Unsatisfied counts, priorities and watches are different quantities. Organising the assignment trail by decision level is what makes non-chronological backtracking expressible at all.

Q: What is non-chronological backtracking?

Conflict analysis identifies the earliest level at which the learned clause becomes unit, and the solver jumps directly there, skipping levels that had nothing to do with the conflict. Chronological backtracking would undo one decision at a time. Clause age, reverse order and restarting are different mechanisms. Returning to the decision actually responsible, rather than the most recent one, is the same idea as conflict directed backjumping in constraint solving.

Q: What is a resolution proof produced by a solver used for?

The proof lets a small independent checker confirm that the clause set really is unsatisfiable, which is essential when the result underwrites a safety argument. It slows the solver and consumes memory rather than saving it, and the proofs are far too large for a human to read. Producing checkable evidence for a claim, so that the producing tool need not be trusted, is the assurance argument in its most concrete form.

Q: What is preprocessing in a satisfiability solver?

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.

Q: What is variable elimination during preprocessing?

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.

Q: Why is preprocessing applied selectively rather than exhaustively?

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.

Q: What is an ontology of inference methods by completeness?

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.

Q: Which methods can establish that a problem has no solution?

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.

Q: What question determines the choice of inference method?

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.

91.

Why does watching two literals suffice?

A.Clauses in practice never contain more than two literals
B.The two watched literals are always the first two in the clause
C.A clause can become unit only when one of the two is falsified
D.Two literals are enough to determine the truth of any clause

Answer: C

So long as two literals remain unassigned the clause is neither unit nor conflicting, so it need not be examined, and only when a watch is falsified must a replacement be sought. Determining truth requires all the literals, clause lengths vary widely, and the watches move during the search. An invariant that guarantees a data structure need not be consulted is exactly what makes lazy updating correct as well as fast.

Discuss in Forum

92.

How is the assignment trail of a solver organised?

A.The number of clauses that remain unsatisfied at present
B.The importance the solver attaches to a particular variable
C.The number of literals watched in each clause of the formula
D.The depth of the current chain of chosen assignments

Answer: D

Each chosen assignment opens a new level, and everything propagated from it belongs to that level, so backjumping means returning to a specified earlier level. Conflict analysis computes which level to return to. Unsatisfied counts, priorities and watches are different quantities. Organising the assignment trail by decision level is what makes non-chronological backtracking expressible at all.

Discuss in Forum

93.

What is non-chronological backtracking?

A.Returning to an earlier level than the most recent decision
B.Backtracking in an order determined by clause age
C.Undoing assignments in the reverse order they were made
D.Restarting the search from the very beginning each time

Answer: A

Conflict analysis identifies the earliest level at which the learned clause becomes unit, and the solver jumps directly there, skipping levels that had nothing to do with the conflict. Chronological backtracking would undo one decision at a time. Clause age, reverse order and restarting are different mechanisms. Returning to the decision actually responsible, rather than the most recent one, is the same idea as conflict directed backjumping in constraint solving.

Discuss in Forum

94.

What is a resolution proof produced by a solver used for?

A.Explaining to a user why the formula has no solution
B.Independent verification of an unsatisfiability result
C.Guiding the search towards a satisfying assignment more quickly
D.Reducing the memory the solver requires during the search

Answer: B

The proof lets a small independent checker confirm that the clause set really is unsatisfiable, which is essential when the result underwrites a safety argument. It slows the solver and consumes memory rather than saving it, and the proofs are far too large for a human to read. Producing checkable evidence for a claim, so that the producing tool need not be trusted, is the assurance argument in its most concrete form.

Discuss in Forum

95.

What is preprocessing in a satisfiability solver?

A.Ordering the clauses so the shortest are considered first
B.Choosing which heuristics the solver will use for this instance
C.Simplifying the clause set before the search begins
D.Reading the formula and converting it into the internal format

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.

Discuss in Forum

96.

What is variable elimination during preprocessing?

A.Deleting a variable that appears in no clause of the formula
B.Assigning a value to a variable chosen before the search starts
C.Renaming variables so that they are numbered consecutively
D.Resolving away a variable when the result is not too large

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.

Discuss in Forum

97.

Why is preprocessing applied selectively rather than exhaustively?

A.Some simplifications enlarge the formula rather than shrinking it
B.Exhaustive preprocessing would not terminate on large formulas
C.Preprocessing may change the satisfiability of the formula
D.The solver cannot search a formula that has been preprocessed

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.

Discuss in Forum

98.

What is an ontology of inference methods by completeness?

A.Completeness and soundness are two names for the same property
B.Complete methods prove absence, incomplete ones only find solutions
C.Complete methods are always faster than incomplete ones in practice
D.Incomplete methods are unsound and may return wrong answers

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.

Discuss in Forum

99.

Which methods can establish that a problem has no solution?

A.Genetic algorithms applied to the space of assignments
B.Any method given sufficient computation time available
C.Systematic search and resolution refutation
D.Local search and simulated annealing over assignments

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.

Discuss in Forum

100.

What question determines the choice of inference method?

A.Which method has performed best on similar problems before
B.How much computing time is available for the search
C.Which method the available software library implements
D.What must be concluded if no solution is found

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.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Inference and Resolution Questions and Answers || Inference and Resolution MCQ Questions and Answers || Inference and Resolution GK Questions and Answers || Inference and Resolution GK MCQ Questions || Inference and Resolution Multiple Choice Questions and Answers || Inference and Resolution GK || GK on Inference and Resolution || Artificial Intelligence Questions and Answers || Artificial Intelligence MCQ Questions and Answers || Artificial Intelligence GK Questions and Answers || GK on Artificial Intelligence

Inference and Resolution Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications