劝说的复杂性结果-计算机科学-机器学习-算法.pdf

劝说的复杂性结果

AlbanGrastien

2025年7月18日

说服是一个由Wojtowicz引入的问题[Woj24]。它在于寻找能够提升特定事实后验概率超过给定阈

值的事实子集。这个问题的应用领域包括“法律、广告、政治、科学、公共关系等”。关于此问题的好

处，我们请读者参阅原始论文。

原文声称问题为np完全问题，并给出了证明。我们认为该证明是不正确的；特别是，他们混淆了

本集合族的空结合与两两空结合。我们证明当说服阈值为时，说服处于p。由于Wojtowicz提出的约减

译使用了一个阈值，这证明了他们的约减是不正确的（我们认为我们的简单计算没有证明p=np）。我们

中提出了一种新的基于原论文中的精确覆盖的证明方法，并展示了在一般情况下的np难性。

1

v

11符号和问题定义

5

9

给定一个集合，我们用表示并用表示。

5

0.一个概率空间是一个三元组，其中是有限集世界们，是一组事件（每个事

7

0件都是世界的子集），以及是在上的概率函数。概率函数的自然扩展到集合是，

5定义为。假设当前（未知）的世界是，它具有非零概率（），并且属

2

:于的交集：。对于不熟悉这种表示法的人来说，事件可以被解释为一个“事实”；向某人

v

i陈述这个事实会告知接收者该现实世界属于集合。

x

r给定一个概率空间，一个观察是事件的子集。事件为真的概率给定一

a

个观察是通过

Prob(1)

计算的请注意该值始终位于和之间；特别是由于属于每个事件，分母严格为正(

)。

A说服问题实例(PPI)是一个三元组其中是一个概率空间，是一个

特定事件，称为目标，而是一个阈值。

A解决方案到PPI与是一个观察，使得Prob。

说服是判断一个PPI是否有解的问题。

关于镜像中的事件进行推理可能会很有用。具体来说，给定事件的有趣之处在于它所包含的世界

集合。我们说它排除或者拒绝这些世界。一个观察结果所拒绝的所有世界都是该观察中至少有一

1

个事件所拒绝的世界。

2强烈说服力

定义1A强说服问题实例（SPPI）是一个PPI，其中阈值评估为。

强烈说服力是说服在SPPIs上的限制。