4

We know that MAJSAT is PP-complete. Is it generally true that given an NP-complete problem, its majority variant is PP-complete? For example,

MAJ-Set-Splitting: are the majority of partitions of items going to split the sets?

MAJ-Subset-Sum: does the majority of partitions of items have a sum of exactly K?

etc...

Spark
  • 371
  • 1
  • 7
  • In the context of Subset-Sum, what do you mean by majority? Do you mean that $K$ is a sum obtained by a maximal number of subsets, or that $K$ is a sum obtained by more than half of the subsets? – Yuval Filmus Jan 07 '15 at 08:51
  • More than half. I got an answer to that from someone: the answer is generally no. The only time that these kinds of properties hold wrt the probabilistic/counting variants of complexity is when the reductions are parsimonious – Spark Jan 07 '15 at 15:28
  • Consider the following example: STUPID-SAT takes as input variables y_1,...,y_n and x_1,...,x_n and a formula F. It's a yes instance if F(x_1,...,x_n) is true and all of y_i are false. Thus, despite STUPID-SAT being NP-c, it always has a minority of its computation paths giving yes, so its MAJ variant is trivial. – Spark Jan 07 '15 at 15:31

2 Answers2

2

MAJ-Subset-Sum is easy to solve. A majority of partitions sum to $K$ iff $K = 0$ and all elements are equal to $0$. Indeed, let $S$ be the (multi)set, and suppose that there were some element $x \neq 0$ in $S$. For each subset $A$ of $S \setminus \{x\}$, either $\sum A \neq K$ or $\sum A + x \neq K$, and so $K$ can be the sum of at most half the subsets. We conclude that if $K$ is a sum of the majority of the subsets that $S$ consists only of zeroes, and so $K = 0$ as well.

Yuval Filmus
  • 276,994
  • 27
  • 311
  • 503
  • Thanks! Though I did give SUBSET-SUM as an arbitrary example of an NP complete problem. I think that in general the answer is that the MAJ variants' difficulty really depends on the type of problem. A general rule is the following: if problem X's MAJ variant is PP-c, and there's a parsimonious reduction from X to Y, then Y's MAJ variant is PP-c as well. – Spark Jan 07 '15 at 15:39
  • @Spark, that parsimonius reduction itself must be easy. If it's #P-hard, you prove nothing. – rus9384 Aug 17 '19 at 10:38
2

The following is based on an answer I got from Piotr Faliszewski, thanks Piotr!

As the example by Yuval shows, things aren't as straightforward. First, one must clearly define what "a majority variant" really means. In most NP-complete decision problems the meaning is quite clear: these problems ask about the existence of some object with a given property and then you can enumerate these objects; "computation paths that return yes" refer to the objects with the property.

The following claim holds: if an NP-complete problem X was shown to be NP-C via a parsimonious many-one reduction from problem Y, for which MAJ-Y is PP-complete, then MAJ-X is PP complete.

In short, a parsimonious reductions guarantees that there is a 1-to-1 mapping between the "computation paths" of the problem we reduce from and the "computation paths" of the problem we reduce to.

Many reductions between standard NP-C problems are known to be parsimonious (and, indeed, such reductions are often easiest to derive).

What happens if you take a problem X which is not NP-C in a parsimonious sense?

Problem: Stupid-SAT

Input : formula $F$ over variables $x_1,..., x_n, y_1, ..., y_n$

Question: Is it possible to set the variables $x_1, ..., x_n, y_1, ..., y_n$ such that:

  1. $F(x_1, ..., x_n, y_1, ..., y_n)$ is satisfied.
  2. all $y_1, ..., y_n$ are set to false

Now, no matter what input formula we have, among the $2^{2n}$ "computation paths", there are at most $2^n$ ones that say yes (provided we are guessing the values for $x$'s and $y$'s, which, while a bit silly, would be a natural interpretation of the statement of the problem).

Thus, there is never a majority of computation paths that say yes and so Maj-Stupid-SAT is an empty set, which certainly is not PP-complete.

Thus, I would be quite careful about saying the if X is NP-C then Maj-X is PP-complete (or even hard; the empty set above is, of course, very easy).

An additional note about counting variants: given an NP-C problem X, define $\#$-X as "how many satisfying paths does an instance of X have?"

Is $\#$-X $\#P$ complete? (e.g. $\#$-TSP = how many routes of length less than k traverse all nodes?)

This also does not have a straightforward answer. There are at least four different (more and more general) notions of $\#P$-completeness.

$\#P$-parsimonious-complete (e.g., $\#$SAT is here)

$\#P$-many-one-complete (e.g., computing Shapley value for WVGs is here, but not above)

$\#P$-metric-complete

$\#P$-Turing-complete

$\#P$-parsimonious-complete is the most restrictive class and $\#P$-Turing-complete is the largest. Some of these classes are known to differ between each other.

When people show hardness, it is easiest to show $\#P$-Turing-completeness and if someone was not careful to mention the exact type of $\#P$-completeness and you do not explore the reduction carefully, the most you can assume is $\#P$-Turing-completeness.

As before, if the problem X was shown to be NP-C in a parsimonious way from a problem Y for which $\#$-Y was $\#P$ complete, then you can certainly claim $\#P$-parsimonious-completeness for $\#$-X. Otherwise, things get complicated.

Indeed, though in a different direction, it is well known that there are poly-time problems whose counting variants are $\#P$-complete (one way or the other).

The very least one can claim, however is the following: if a problem X is NP-C, then certainly $\#$-X is hard in some computational way (indeed, if it were easy then solving X would be easy too).

Spark
  • 371
  • 1
  • 7
  • "indeed, if it were easy then solving X would be easy too" It would be interesting to see FNP-complete counting problem. – rus9384 Aug 17 '19 at 10:51