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