7
j
=1
因此，获得上界近似的一种自然方法是将g（x）替换为
常数
1
，这相当于用
Y
代替了
k
T
i
。 设
f
′
：
{0
，
1}
n
→ { 0
，
1}
为
J
通过此替换获得的DNF公式显然
f
（x）≤
f
′
（x）。此外，本发明还
Pr[f
（
x
）
= 0 f
′
（
x
）
= 1] ≤Pr [g
（
x
）
= 0] ≤
ε
。
x x
m
最后，我们有s（f
′
）≤s（f）−（k−1）。
我们现在可以迭代地应用上面的论点，只要项数是
大于等式（2.1）中的边界。在每次迭代中，我们将s（f）减少k−1。因此，我们重复该过
程至多m/（k-1）次，获得上近似公式f
u
，其中
f
（
x
）
≤
f
u
（
x
）
<$
x
∈ {0
，
1}
n
，
Pr[f
（
x
）
/=f
u
X
m ε
（
x
）
]
≤
·
.
k
−
1
m
。
=
ε
，
ΣΣ
s（f
u
）≤
w2
w
ln
m
w
.
ε
下面我们描述下近似公式
f
的构造。我们从向日葵
T
i
1
，
···
，
T
i
k
开始，核心是
Y
。现在
考虑从
f
中去掉一项得到的公式
f
′′
，比方说
Ti
1
。则
f
′′
（x）≤
f
（x）。此外，它们两者仅在
f
′′
（
x
）
= 0
和
f
（
x
）
= 1
时不同，这发生在
Ti
1
= 1
而
Ti
j
= 0
时，
j
∈ {2
，
. . .
，
k}
。因此，
我们可以将这个概率限制为：
Pr
[
f
′′
（
x
）
/=
f
（
x
）
]=
Pr
[
T
i
= 1]
·
Pr[
（
k
T
i
）
= 0|
我
不是
= 1]
x x
j
1
x
j
=2
j
J
1 .
一
、
1
k
−1
ε
=Pr[
（
k
T
i
\Y
）
= 0]= 1− ≤
2
x
j
=2
j
2 2
W
M
其中第二个不等式成立，因为根据向日葵的性质，条件T
i
1
= 1固定了核心Y= 1，但不影响
其他花瓣。注意s（f
′′
）≤s（f）−1。我们现在将这一步重复不超过m次，以获得公式f，
其中
f
<$
（
x
）≤
f
（
x
）<$
x
∈ {0
，
1}
n
，
Pr[f
]
（
x
）
ε
f
（x）]≤m
·
=
ε
，
X
.
M
.
ΣΣ
s（f
u
）≤
w2
w
ln
m
w
.
ε
定理2.1比定理1.1在不确定性、对m的依赖性和对w的依赖性方面弱。我们简单地描述
一下如何处理前两个问题。
1.
不和谐。
我们可以通过使用引理
2.7
来去除这个假设，它保证了任何
DNF
公式都包
含一个大子公式。由此产生的语句对于推论1.3已经足够了，因为任何宽度为log
（
n
）的
DNF
最多可以有
n
个
O
（
log
（
n
）
）的子句。
剩余34页未读，继续阅读
cpongm
- 粉丝: 5
- 资源: 2万+
我的内容管理
展开
最新资源
- 岩石滑动与断层冲击地压：声发射特征分析
- 新时代煤炭工业八大战略新取向剖析
- 开采强度对华亭矿区冲击地压危险性的影响分析
- 新安煤矿探采对比：影响安全生产的关键因素与技术支撑
- 210MW循环流化床锅炉引风机变频改造优化与节能效果
- 浅埋煤层开采沉陷预测：方法应用与影响分析
- 优化巷道过陷落柱支护方案：数值模拟与现场试验
- 坚硬顶板定向断裂爆破技术：安全高效采煤新方案
- 北航2019算法课作业解析：投资策略与凸子多边形优化
- 断层破碎带垮冒下堆积体边界抗力分布关键影响因素
- 哈拉沟选煤厂优化末煤系统提高效率与处理能力
- 瓦斯涌出影响下采动煤体蠕变失稳研究
- 提升煤矿装载效率的可控箕斗定量装载设备设计
- 水分调控下烟煤瓦斯吸附特性对比研究
- 重介质悬浮液密度控制硬件设计与选型探讨
- 坚硬顶板巷道支护参数设计：现场测试与数值分析
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
