Complexity Results of Persuasion

Alban Grastien · 2025

Read Complexity Results of Persuasion by Alban Grastien (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-05951.txt.

Introduction

Alban Grastien revisited in 2025 the complexity of a problem called persuasion, introduced in earlier work. The problem asks for a subset of facts that raises the probability of a target fact past a set threshold. It has uses in fields such as law, advertising, and politics.

The original paper claimed the problem is NP-complete, but Grastien shows its proof was flawed, mixing up two different notions of empty overlap. He proves the problem sits in the class P when the threshold is one, which breaks the original reduction. He then gives a new proof, built on exact cover as in the original, that the general problem is NP-hard. The paper is a correction as much as a new result.

Catalog record

CREATORAlban Grastien
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE12 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-05951

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Complexity Results of Persuasion Alban Grastien Abstract Persuasion is a problem introduced by Wojtowicz [ Woj24 ] . It consists in finding a subset of facts that improves the a-posteriori probability of a specific fact over a given threshold. It has applications in “law, advertising, politics, science, public relations, etc”. We refer the reader to the original paper for a discussion about the benefits of this problem. The original paper claims that the problem is np-complete and presents a proof. We claim that that proof was incorrect; in particular, they make a confusion between the empty conjunction of a collection of sets and the pairwise empty conjunction. We prove that persuasion is in p when the persuasion threshold is 1 . As the reduction proposed by Wojtowicz uses with value for threshold, this proves the incorrectness of their reduction (we do not believe that p = np is proved by our simple computations). We propose a new proof based, as in the original paper, on exact cover and show np-hard ness in the general case. 1 Notation and Problem Definition Given a set S=\{S_{1},\dots,S_{k}\} of sets, we use \bigcap S to denote S_{1}\cap\dots\cap S_{k} and \bigcup S to denote S_{1}\cup\dots\cup S_{k} . A probability space is a triple P=\langle\Omega,F,\pi\rangle where \Omega is a finite set of worlds , F\subseteq 2^{\Omega} is a set of events (each event is a subset of worlds), and \pi:\Omega\mapsto[0,1] is a probability function over \Omega . The natural extension of probability function \pi to sets is \pi^{*} and is defined by \pi^{*}(S)=\sum_{\omega\in S}\ \pi(\omega) . It is assumed that the current (unknown) world is \omega^{\star} , that it has a non-zero probability ( \pi(\omega^{\star})>0 ), and that it belongs to the intersection of F : \omega^{\star}\in\bigcap F . For people who are not familiar with this notation, an event f can be interpreted as a “fact”; stating this fact to someone informs the recipient of the statement that the real world \omega^{\star} belongs to the set f . Given a probability space P=\langle\Omega,F,\pi\rangle , an observation is a subset R\subseteq F of events. The probability that an event e\subseteq\Omega is true given an observation R is calculated by \mathrm{Prob}(e\ |\ R)=\frac{\pi^{*}(e\cap\bigcap R)}{\pi^{*}(\bigcap R)}. (1) Note that the value always sits between 0 and 1 ; in particular since \omega^{\star} belongs to each event r\in R , the denominator is strictly positive ( \pi^{*}(\bigcap R)\geq\pi(\omega^{\star})>0 ). A persuasion problem instance (PPI) is a triple \langle P,E,\tau\rangle where P=\langle\Omega,F,\pi\rangle is a probability space, E\subseteq\Omega is a particular event called the goal , and \tau\in[0,1] is a threshold . A solution to PPI \langle P,E,\tau\rangle with P=\langle\Omega,F,\pi\rangle is an observation R such that \mathrm{Prob}(E\ |\ R)\geq\tau . Persuasion is the problem of deciding whether a PPI has a solution. It can be useful to reason about events in mirror. Specifically, what is interesting about a given event f is the set \Omega\setminus f of worlds that it does contain. We say that it excludes or rejects these worlds. The worlds rejected by an observation are all the worlds rejected by at least one event in the observation. 2 Strong Persuasion Definition 1 A strong persuasion problem instance (SPPI) is a PPI where the threshold \tau evaluates to 1 . Strong Persuasion is the restriction of Persuasion to SPPIs. It is possible to prove that there is a solution to the strong persuasion problem iff R=F is a solution, i.e. \bigcap F\subseteq E holds. Corollary 1 Strong Persuasion is in P . If one wanted to drop the condition that the intersection of F is not empty (but that would be silly), we could use the following property: An SPPI admits a solution iff there exists \omega in E such that R_{\omega}=\{r\in F\mid\omega\in r\} is a solution. Thus, it is possible to go through all elements of E and check in polynomial time whether they yield a solution observation. 3 Complexity of Persuasion Wojtowicz proposes a proof of np-hard ness complexity for Persuasion , but this proof includes an error. Specifically, they provide a reduction from Exact Cover (defined next subsection) in which they prove that the intersection of the computed sets is empty; however, the problem definition requires every pair of set to be disjoint. We provide a corrected proof here. 3.1 Exact Cover To prove the complexity of Persuasion , we use a reduction from the np-complete problem Exact Cover which we present now. An Exact Cover Instance (ECI) is a pair \langle S,A\rangle where S=\{s_{1},\dots,s_{n}\} is a finite set of objects and A=\{A_{1},\dots,A_{k}\} is a set of (non-empty, pairwise different) subsets of S such that \bigcup A=S holds. Elements from S are called universe elements and indices ranging between 1 and n are universe indices . A solution to ECI \langle S,A\rangle is a subset H of A that forms a partition of S , i.e., • \forall\{A_{i},A_{j}\}\subseteq H.\ A_{i}\cap A_{j}\neq\emptyset\Rightarrow A_{i}=A_{j} and • \bigcup_{A_{i}\in\mathcal{A}}\ A_{i}=S . (A partition should include no empty set, but this is trivially satisfied here as A has no empty set.) Exact Cover is the problem of deciding whether there is a solution to an ECI; it is np-complete . 3.2 Reduction We now propose a reduction from Exact Cover to Persuasion . We start with a description of the reduction and give the formal definition afterwards. Our reduction introduces four types of worlds: • W_{0} and X_{0} are two worlds that cannot be rejected by an observation. W_{0} belongs to goal E while X_{0} does not. These two worlds guarantee that we never get any solution with 0 or 1 probability. • Z -variables are mapped with universe elements. They do not belong to goal E . • Y -variables are mapped with pair \langle i,\ell\rangle such that s_{\ell}\in A_{i} . They belong to goal E . The events are defined to match the sets of A . The event F_{i} (associated with A_{i} ) will exclude precisely all Y -variables that mention i and all Z -variables mapped with a universe element of A_{i} . The probabilities of these variables are set in such a way that the probability of goal E given observation R is attained iff the following two conditions are satisfied: 1. All Z -variables are excluded from observation R . This guarantees that the observation matches a cover of S . Remember that Z -variables do not belong to goal E ; thus, giving them a high enough probability will penalise \mathrm{Prob}(E\ |\ R) if they are not rejected. 2. Exactly n Y -variables are excluded from observation R . This guarantees that a given universe element is not excluded by two different events from the observation: thus the cover is exact. As Y -variables belong to goal E , solutions are naturally better when they do not exclude them; yet their probability is set to a low value so that this objective is superseeded by the first one (which guarantees the solution is a cover). Our proposed reduction is presented on Fig. 1 . Reduction Let \langle S,A\rangle be an ECI where S=\{s_{1},\dots,s_{n}\} and A=\{A_{1},\dots,A_{k}\} . Let m=\sum_{i\in\{1,\dots,k\}}\ |A_{i}| be the number of elements in the subsets of A . We define the PPI

Read the complete text