# On Strong NP-Completeness of Rational Problems

arXiv: https://arxiv.org/abs/1802.09465 · HTML: https://mlsanity.com/paper/1802.09465/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2018.

## Built on by (most cited first, 3 of 3)

- [Towards An Efficient Approach for the Nonconvex ℓp Ball Projection: Algorithm and Analysis](https://mlsanity.com/paper/2101.01350/) (2021)
- [Time Fairness in Online Knapsack Problems](https://mlsanity.com/paper/2305.13293/) (2023)
- [KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems](https://mlsanity.com/paper/2509.15239/) (2025)

## Abstract (arXiv)

The computational complexity of the partition, 0-1 subset sum, unbounded subset sum, 0-1 knapsack and unbounded knapsack problems and their multiple variants were studied in numerous papers in the past where all the weights and profits were assumed to be integers. We re-examine here the computational complexity of all these problems in the setting where the weights and profits are allowed to be any rational numbers. We show that all of these problems in this setting become strongly NP-complete and, as a result, no pseudo-polynomial algorithm can exist for solving them unless P=NP. Despite this result we show that they all still admit a fully polynomial-time approximation scheme.