1
$\begingroup$

Exercise 3 from https://massimolauria.net/courses/2015.ProofComplexity/lecture6.pdf

Consider the set of inequalities $x_i+x_j\leq1$ for $1\leq i<j\leq n$.

Find a derivation of $\sum_{i=1}^n x_i\leq 1$ in $O(n^2)$ length.

If it were just algebra I could just show by contradiction that at most one $x_i$ could be 1 and be done but how does it translate it into cutting planes PS? I guess a similar idea would be by obtaining $\sum_{i=1}^n x_i \leq n-1 -(n-2)x_i$ for all $i$ through addition of $x_i+x_j$ for all $1\leq j\leq n$ but I'm stuck there.

Thanks for your help.

$\endgroup$

1 Answer 1

2
$\begingroup$

The proof is by induction. Here is the inductive step.

Suppose that we know both of the following inequalities: $$ x_1 + \cdots + x_m \leq 1 \\ x_2 + \cdots + x_{m+1} \leq 1 $$ Add them to get $$ x_1 + 2x_2 + \cdots + 2x_m + x_{m+1} \leq 2 $$ Add the axiom $x_1 + x_{m+1} \leq 1$ to get $$ 2x_1 + \cdots + 2x_{m+1} \leq 3 $$ Divide by 2 and round down to get $$ x_1 + \cdots + x_{m+1} \leq 1 $$ I'll let you fill in the remaining details.

$\endgroup$
6
  • $\begingroup$ Thanks. Adding everything up would then prove a refutation for the pigeonhole principle in O(n^3), right? $\endgroup$
    – Mark Regev
    May 28, 2020 at 9:44
  • $\begingroup$ The length of a proof is the number of lines in the proof. Make sure to get your definitions right! $\endgroup$ May 28, 2020 at 9:46
  • $\begingroup$ I have another question regarding exercise 4, rank of the derivation. Could you give me a hint on how to divide the variables to reach a logarithmic rank? $\endgroup$
    – Mark Regev
    May 28, 2020 at 10:33
  • $\begingroup$ Go from $n$ to $2n$. $\endgroup$ May 28, 2020 at 10:58
  • $\begingroup$ If I add x_1+...+x_n<=1 ... x_n+...+x_2n<=1 and wrap around I get n*sum(2n) <= 2n. How do you push it to 1? $\endgroup$
    – Mark Regev
    May 28, 2020 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.