Inference and Resolution Questions and Answers

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.

Q: What is the relationship between resolution and satisfiability solving?

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.

Q: Why does that connection matter in practice?

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.

Q: What do pigeonhole formulas demonstrate?

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.

Q: What follows from a proof complexity lower bound for a proof system?

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.

91.

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

92.

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

93.

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

94.

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

95.

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

96.

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

97.

What is the relationship between resolution and satisfiability solving?

A.A conflict driven solver constructs a resolution proof implicitly
B.The two are unrelated approaches to different kinds of problem
C.Resolution is used only for first order and solving for propositional logic
D.Satisfiability solving replaced resolution entirely in modern practice

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.

Discuss in Forum

98.

Why does that connection matter in practice?

A.It shows the solver will always terminate in polynomial time
B.Proof complexity results bound what any such solver can achieve
C.It allows the solver to be replaced by a resolution prover
D.It means the solver can be used for first order problems

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.

Discuss in Forum

99.

What do pigeonhole formulas demonstrate?

A.Resolution is unsound for certain classes of formula
B.Satisfiability is decidable only for small formulas
C.Some formulas require exponentially long resolution proofs
D.Some formulas cannot be written in conjunctive normal form

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.

Discuss in Forum

100.

What follows from a proof complexity lower bound for a proof system?

A.The formulas concerned have no proofs in any system at all
B.The proof system is unsound and should not be used
C.Every formula in that system requires exponential time
D.No algorithm searching that system can be efficient on those formulas

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.

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