Question

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

Answer 1

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 x1,...,xn,y1,...,yn

Question: Is it possible to set the variables x1,...,xn,y1,...,yn such that:

F(x1,...,xn,y1,...,yn) is satisfied.
all y1,...,yn are set to false

Now, no matter what input formula we have, among the 22n "computation paths", there are at most 2n 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).