TLDR: This research paper re-examines the computational complexity of the “persuasion problem,” which involves influencing the probability of a specific fact. It corrects a previous proof, demonstrating that persuasion is efficiently solvable (in P) when the influence threshold is 1. However, the paper also provides a new, corrected proof, showing that the general persuasion problem remains NP-hard, confirming its computational difficulty for broader applications.
The concept of persuasion, as introduced by Wojtowicz, revolves around identifying a subset of facts that can enhance the a-posteriori probability of a specific fact beyond a predetermined threshold. This problem has wide-ranging applications across various domains, including law, advertising, politics, science, and public relations.
The original research claimed that the persuasion problem was NP-complete, a classification indicating its computational difficulty. However, this new research paper, titled “Complexity Results of Persuasion,” challenges that initial proof. The authors, Alban Grastien, argue that the original proof contained an error, specifically a confusion between the empty conjunction of a collection of sets and the pairwise empty conjunction.
Strong Persuasion: A Simpler Case
A significant finding in this paper is that when the persuasion threshold is set to 1, the problem, termed “Strong Persuasion,” is actually in P (polynomial time). This means that for a threshold of 1, the problem can be solved efficiently. This result directly contradicts the implications of Wojtowicz’s original reduction, which, if correct, would suggest that P=NP, a major unsolved problem in computer science.
The General Case: Still NP-Hard
Despite the efficient solvability of Strong Persuasion, the paper confirms that the general persuasion problem remains NP-hard. To establish this, the authors propose a new, corrected proof based on a reduction from the well-known NP-complete problem called Exact Cover.
Exact Cover is a problem where, given a collection of sets, the goal is to find a sub-collection such that each element of a universe set is contained in exactly one of the chosen sets. This problem is known to be computationally challenging.
Also Read:
- Bridging Probability and Logic: A New Look at Rational Beliefs and Their Evolution
- Navigating Accountability: Understanding Responsibility Gaps and Diffusion in AI Decision-Making
Understanding the Reduction
The new reduction from Exact Cover to Persuasion involves constructing a specific probability space with four types of “worlds”: W0, X0, Z-variables, and Y-variables. W0 and X0 are designed to ensure that solutions do not have trivial 0 or 1 probabilities. Z-variables are linked to universe elements and are not part of the goal, while Y-variables are associated with specific set-element pairs and are part of the goal.
The events within this probability space are defined to exclude certain Y and Z variables. The probabilities assigned to these worlds are carefully calibrated. The paper demonstrates that the probability of the goal event (E) given an observation (R) meets the required threshold if and only if two key conditions are satisfied:
1. All Z-variables are excluded by the observation. This condition ensures that the observation effectively “covers” all universe elements from the Exact Cover problem.
2. Exactly a specific number of Y-variables are excluded. This condition guarantees that the cover is “exact,” meaning there are no overlaps between the chosen sets.
Through a series of rigorous proofs, the paper establishes that if a set of facts provides a solution to the persuasion problem instance, then the corresponding sets form an exact cover for the Exact Cover instance. This reduction solidifies the conclusion that the general persuasion problem is indeed NP-hard, reinforcing its inherent computational complexity. For more details, you can refer to the original research paper.
