Source-linked AI summary
Feasible disjunction for random resolution
Theodoros Papamakarios
TL;DR
The paper addresses whether feasible disjunction can hold for a proof system not known to have feasible interpolation. It studies random resolution with dynamic error and proves feasible disjunction for this stronger version, while noting limitations of the error notion and its implications.
Problem
Feasible interpolation is important in proof complexity, but whether a system can have feasible disjunction without being known to have feasible interpolation remains a question.
Source: §1 · pp. 1–2Method
Results
If F ∧G has a dynamic-error random resolution refutation of size s and error ε, one of F or G has such a refutation of error at most ε and size sO(1+log(1/ε)).
Source: §3 · p. 5Takeaways & Limitations
This gives an example of a proof system with feasible disjunction for which feasible interpolation is not known.
Source: §1 · p. 2The lower-bound fixing-lemma argument for DAG-like static-error random resolution does not seem to transfer immediately to dynamic error.
Source: §4 · p. 6
Abstract
from arXiv · showhide
We show that a (stronger) version of random resolution has the feasible disjunction property. This is the first instance of a proof system not known to have feasible interpolation, which nevertheless has the feasible disjunction property.
1. Introduction
The paper identifies an extension of random resolution with feasible disjunction, although feasible interpolation is not known for it. The result uses a minimax argument that yields an exponentially supported distribution rather than a polynomial-time constructive proof.
1. Introduction
- Feasible interpolation matters because it gives conditional lower bounds, while its failure implies that short refutations are hard to find.The lower-bound connection is conditional, or unconditional for monotone feasible interpolation; cited works are and.Source: §1 · p. 1
- For disjoint-variable F and G, feasible disjunction requires that a refutation of F ∧G yield a polynomial-size refutation of one of them.The introduction also describes deciding in polynomial time which formula is unsatisfiable.Source: §1 · p. 1
- Feasible interpolation typically brings feasible disjunction, but feasible disjunction fails for Res(2), where feasible interpolation also seems to fail.In known cases, interpolation arguments can often be modified to produce a refutation of one disjunct; the Res(2) result is.Source: §1 · p. 1
- Unlike feasible interpolation, feasible disjunction is not downward closed under p-simulation.The paper points to restricting a proof system with both properties to obtain a subsystem where feasible disjunction fails.Source: §1 · pp. 1–2
- An extension of random resolution has feasible disjunction, although feasible interpolation is not known for it.The proof uses the minimax theorem and produces a distribution over assignments with exponential support, so the authors do not see how to make the proof polynomial-time constructive.Source: §1 · p. 2
2. Random resolution refutations
Random resolution represents a refutation as a distribution over resolution proofs for a formula conjoined with auxiliary CNFs. The section distinguishes static error from traversal-based dynamic error and records soundness, error-reduction, and interpolation-related properties.
2. Random resolution refutations
- A random resolution refutation samples a CNF B_i and a resolution refutation of F ∧B_i; dynamic error measures traversal failure, unlike static error, which measures when B_i is true.The traversal models a search procedure that, given an assignment, follows a sampled proof to find a falsified clause.Source: §2 · pp. 2–3
- A random resolution refutation with static or dynamic error ε<1 proves F unsatisfiable and can be sampled on a uniform space of size O(n/ε) with error at most 2ε.Here n is the number of variables of F.Source: §2 · p. 3
- Repeating random refutations can reduce error to ε^k, with proof size O(s1 ··· sk) for each tuple of sampled proofs.The stated error reduction applies to either static or dynamic error.Source: §2 · p. 3
- Dynamic error is at most static error, making random resolution with static error ε a weaker system than its dynamic-error counterpart at ε.Consequently, feasible interpolation for the dynamic-error system would imply it for the static-error system.Source: §2 · p. 3
- Earlier interpolation-related models for static-error random resolution do not provide a polynomial-time interpolating algorithm.The discussion covers communication protocols and circuit-separation approaches, including,, and.Source: §2 · p. 3
3. Feasible disjunction for random resolution with dynamic error
The section proves that a dynamic-error random resolution refutation of F ∧ G yields a refutation of one side, then uses this result to establish feasible disjunction. The proof compares the two sides’ success rates through a minimax argument and gives a size bound for restoring the original error.
3. Feasible disjunction for random resolution with dynamic error
- Using von Neumann’s minimax theorem, the two sides’ success guarantees satisfy VF+VG≥1−ε; therefore at least one side has success rate at least (1−ε)/2.Source: §3 · p. 4
- A size-s refutation of F ∧ G with dynamic error ε yields a size-s refutation of F or G with dynamic error at most (1 + ε)/2.The formulas are CNFs with disjoint variables, and F ∧ G is unsatisfiable.Source: §3 · pp. 4–5
- For ε ∈ (0, 1), the error can be restored to at most ε with a refutation of size s^O(1+log(1/ε)), establishing feasible disjunction.The theorem’s intermediate success-rate drop does not prevent this error reduction.Source: §3 · p. 5
4. Concluding remarks
The authors identify random resolution with dynamic error as a proof system with feasible disjunction, although whether it has feasible interpolation remains open. They also describe limits on generalizing the result and identify open questions about lower bounds and equivalence with static-error random resolution.
4. Concluding remarks
- Random resolution with dynamic error has feasible disjunction, while whether it has feasible interpolation remains open.Source: §4 · p. 5
- If random resolution had feasible interpolation, resolution over parities would too, linking this question to Res(⊕)'s interpolation boundary.Source: §4 · p. 5
- A depth-2 Frege refutation has dynamic error 0 but static error 1, illustrating how dynamic error can trivialize random versions of stronger systems.Source: §4 · p. 5
- Tree-like versions of static- and dynamic-error random resolution coincide, but prior DAG-like lower bounds do not immediately transfer to dynamic error.The fixing-lemma step in those lower-bound arguments appears to require static error.Source: §4 · pp. 5–6
- Open directions include proving exponential lower bounds for dynamic error and determining whether the static- and dynamic-error systems are polynomially equivalent.Source: §4 · p. 6