Subset Sum → Product Knapsack with unary profits and binary weights Complexity open
Unsolved
Why this question matters
Moderate: hardness would settle a natural encoding boundary in multiplicative knapsack and could transfer to tournament-bribery models through the published Product Knapsack connection, provided their probability restrictions match. It would not alone prove every such bribery variant hard.
The IJCAI 2024 paper explicitly says that NP-hardness of Product Knapsack with unary item values and binary item sizes is open. Its weak hardness theorem and W[1]-hardness for unrestricted binary profits do not settle this encoding.
The reduction to construct
The input is a list of positive binary-encoded integers a_i and a binary target T. Output YES exactly when some subset sums to T, and NO otherwise.
The input is a list of items with positive integer weights written in binary and positive integer profits written in unary, plus binary-encoded capacity C and product threshold V. Output YES exactly when some subset has total weight at most C and product of its profits at least V; otherwise NO.
Construct deterministic polynomial-time F and G from Subset Sum to this unary-profit Product Knapsack restriction, preserving YES and NO. A positive result would prove NP-hardness for the encoding boundary explicitly left open in the tournament-bribery literature.
High: known weak-hardness reductions encode large numeric leverage in item profits, which becomes exponentially long in unary. A possible route makes binary weights carry the Subset Sum choices while constant or polynomial unary profits enforce cardinality and consistency; the missing step is obtaining an exact product gap without exponential replication.
What a complete answer must include
Give explicit item weights, unary profits and thresholds; prove both answer directions and bound the total unary output length and binary arithmetic. Later independent checks should enumerate small item subsets.
References
Literature checked 2026-09-26. Checked IJCAI 2024 paper, Section 3 Product Knapsack results and Conclusion, and searched 2026-09-26 for 'Product Knapsack unary values binary sizes NP-hard' and 2025-26 follow-ups. No direct resolution surfaced in indexed coverage; this is not proof of global openness. Gates 1-4 pass within this coverage; Gate 5 holds pending a polynomial-unary gap construction; Gate 6 was not assessed.