patternMinor
MAX,MAJ variants of NP complete problems
Viewed 0 times
majvariantscompletemaxproblems
Problem
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-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...
Solution
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.
Context
StackExchange Computer Science Q#36023, answer score: 2
Revisions (0)
No revisions yet.