4
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Jan 7 '15 at 8:51
  • $\begingroup$ 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 $\endgroup$ – Spark Jan 7 '15 at 15:28
  • $\begingroup$ 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. $\endgroup$ – Spark Jan 7 '15 at 15:31
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Spark Jan 7 '15 at 15:39
  • $\begingroup$ @Spark, that parsimonius reduction itself must be easy. If it's #P-hard, you prove nothing. $\endgroup$ – rus9384 Aug 17 at 10:38
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ "indeed, if it were easy then solving X would be easy too" It would be interesting to see FNP-complete counting problem. $\endgroup$ – rus9384 Aug 17 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.