互补松弛定理
【一、定理内容：】
定理1：对于一个一般化的原始—对偶问题，
---------
原始LP（linear programming）
max cx
s.t. Ax <= b, x >=0
---------
对偶LP
min by
s.t. A^Ty >= c, y >= 0
--------
其中A是一个mxn的矩阵（注：即对于原始问题有m个约束、n个变量）
另x是原始LP的一个可行解，另y是对偶问题的一个可行解。那么：
x和y同时是其对应LP最优解，当且仅当：
1）对于1<i<m，或者 yi = 0 或者 bi - 求和_{j=1到n} aijxj = 0 或者 两个同时成立。
注意到 bi - 求和_{j=1到n} aijxj 是原始LP的第i个约束的松弛量。
2）对于1<j<n，或者 xj = 0 或者 求和_{i=1到m} aijyi - cj = 0 或者 两个同时成立。
注意到 求和_{i=1到m} aijyi - cj 是对偶LP的第j个约束的松弛量。
证明如下：
x和y是对应LP的最优解
<=> （由weak duality可得？？）
c^Tx = y^Tb
<=>（由weak duality的证明，即c^Tx <= y^TAx <= y^Tb，可得）
c^Tx = yTAx 以及 y^TAx = y^Tb
<=>（有代数运算可得）
(ATy - c)^Tx = 0 以及 y^T(b - Ax) = 0
<=> （下面再解释）
互补松弛定理条件成立
最后一个等式是由于A^Ty - c, x, y, 和 b - Ax 都是非负的，所以他们的点击为零的条件只能是对应元素为0时才可能成立。
【二、举个例子】
互补松弛定理可以用来验证给定的某个解是否是最优解：
【例1】：假设某个人告诉我们x1* = 9/7， x2* = 0， x3* = 1/7 是下面LP问题的最优解：
max x1 - 2x2 + 3x3
s.t. x1 + x2 - 2x3 <= 1, (a)
__2x1 - x2 - 3x3 <=4, (b)
___x1 + x2 + 5x3 <= 2. (c)
x1, x2, x3 >= 0.
【
注：对应的对偶问题如下：
min y1 + 4y2 + 2y3
s.t. y1 + 2y2 + y3 >= 1, (d)
___y1 - y2 + y3 >= -2, (e)
__-2y1 - 3y2 + 5y3 >= 3 (f)
】
现在来验证一下：
首先这个解满足所有约束。
接着看一下用互补松弛定理能否得到对偶问题的最优解y1*, y2*, y3*.
由于x1*, x3* 不为0，则由定理的2)可得对偶问题的第1和第3个约束（注：d和f）没有松弛量：
_y1 + 2y2 + y3 = 1,
-2y1 - 3y2 + 5y3 = 3,
现在有两个等式方程，却有三个变量！
接着再检查一下原始问题，看一下所谓的最优解在原始问题约束中的松弛量。可以发现第2个约束（注：b）存在松弛量（也就是2x1* - x2* - 3x3* = 15/7 < 4），因此由定理的1)可得对偶问题的第2个变量y2* = 0。
加上这个条件，原来的方程组就变成：
y1* + y3* = 1
-2y1*+5y3* = 3
这里唯一的解就是y1* = 2/7， y3* = 5/7，那么有了这些是否一定就是最优解呢？
最后再用互补松弛定理验证一下。
首先验证y1*, y2*, y3*在对偶LP里是否可行，其次再验证对应的互补松弛性，如果都满足，就可以认定确实x1*,x2*,x3*是最优解。
【例2】：假设有人告诉我们x1* = 9/7, x2* = 0, x3* = 1/7是下面这个LP的最优解：
max x1 + 2x2 + 3x3
s.t. x1 + x2 - 2x3 <= 1, (a)
__2x1 - x2 - 3x3 <=4, (b)
___x1 + x2 + 5x3 <= 2. (c)
x1, x2, x3 >= 0.
（唯一的不同在于目标函数里x2的系数！）
同样和例1一样，可以得到y*, 但是这个时候对偶问题不可行，所以x*并不是最优解。

原文：paper
题目：Commitment Schemes and Zero-KnowledgeProtocols
（承诺协议与零知识协议）
摘要：这篇文章介绍了两个应用于密码学协议理论中的基础工具：承诺协议和零知识协议，并且研究了基于这两这及其联系的相关结果，包括已有结论和新提出的结论。