Inference and Resolution Questions and Answers

Q: What is the phase transition in random satisfiability problems?

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.

Q: Why are instances far from the critical ratio easy?

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.

Q: What is a proof by refutation?

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.

Q: What is a proof by contradiction in everyday mathematical terms?

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.

Q: What is an implication graph in a satisfiability solver?

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.

Q: What is a decision variable in a satisfiability search?

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.

Q: How does a solver choose which variable to decide on?

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.

Q: What is a saturation based theorem prover?

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.

Q: What is the given clause algorithm?

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.

Q: Why must clause selection be fair in a saturating prover?

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.

31.

What is the phase transition in random satisfiability problems?

A.The formula changes from conjunctive to disjunctive normal form
B.The problem becomes decidable above a certain number of variables
C.Hard instances cluster at a critical ratio of clauses to variables
D.The solver switches from systematic to local search at a threshold

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.

Discuss in Forum

32.

Why are instances far from the critical ratio easy?

A.Such instances contain fewer variables than critical ones
B.The solver's heuristics are tuned for those regions
C.The formulas can be simplified to propositional form
D.Solutions are abundant below it and contradictions obvious above it

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.

Discuss in Forum

33.

What is a proof by refutation?

A.Deriving a contradiction from the premises and the negated goal
B.Showing that the goal is false in some particular model
C.Refuting an opponent's argument rather than proving one's own
D.Deriving the goal directly from the premises by forward inference

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.

Discuss in Forum

34.

What is a proof by contradiction in everyday mathematical terms?

A.Demonstrating that a counterexample cannot be constructed
B.Assuming the negation and deriving an impossibility
C.Showing that two premises contradict one another directly
D.Proving a statement by proving its contrapositive instead

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.

Discuss in Forum

35.

What is an implication graph in a satisfiability solver?

A.A diagram of the clause set's structure before solving
B.A graph whose nodes are clauses and edges resolutions
C.A record of which assignments forced which others
D.A graph of the implications appearing in the formula

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.

Discuss in Forum

36.

What is a decision variable in a satisfiability search?

A.One appearing in the largest number of clauses
B.One whose value determines the satisfiability of the formula
C.One that has been assigned by the pure symbol rule
D.One assigned by choice rather than forced by propagation

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.

Discuss in Forum

37.

How does a solver choose which variable to decide on?

A.By a heuristic favouring variables involved in recent conflicts
B.By taking the variables in the order they appear
C.By selecting whichever variable has the largest domain remaining
D.By choosing randomly with uniform probability each time

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.

Discuss in Forum

38.

What is a saturation based theorem prover?

A.One deriving only the consequences needed for the goal
B.One deriving all consequences under a strategy until nothing is new
C.One that stops as soon as the search space is saturated with clauses
D.One that fills its memory before beginning to search

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.

Discuss in Forum

39.

What is the given clause algorithm?

A.Choosing a clause at random and resolving it once
B.Processing clauses strictly in the order they were derived
C.Selecting one clause and resolving it against all previously kept clauses
D.Resolving every pair of clauses in the set at each iteration

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.

Discuss in Forum

40.

Why must clause selection be fair in a saturating prover?

A.Otherwise the prover would use too much memory
B.Otherwise the clauses would be derived in the wrong order
C.Otherwise subsumption could not be applied correctly
D.Otherwise some clause might never be selected and a proof missed

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.

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