HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

MAX,MAJ variants of NP complete problems

Submitted by: @import:stackexchange-cs··
0
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...

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.