# On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2025.

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

- [Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations](https://mlsanity.com/paper/2610.14996/) (2026)

## Abstract (arXiv)

In the knapsack problem under explorable uncertainty, we are given a knapsack instance with uncertain item profits. Instead of having access to the precise profits, we are only given uncertainty intervals that are guaranteed to contain the corresponding profits. The actual item profit can be obtained via a query. The goal of the problem is to adaptively query item profits until the revealed information suffices to compute an optimal (or approximate) solution to the underlying knapsack instance. Since queries are costly, the objective is to minimize the number of queries. In the offline variant of this problem, we assume knowledge of the precise profits and the task is to compute a query set of minimum cardinality that a third party without access to the profits could use to identify an optimal (or approximate) knapsack solution. We show that this offline variant is complete for the second-level of the polynomial hierarchy, i.e., Sigma2p-complete, and cannot be approximated within a non-trivial factor unless Sigma2p = Delta2p. Motivated by these strong hardness results, we consider a resource-augmented variant of the problem where the requirements on the query set computed by an algorithm are less strict than the requirements on the optimal solution we compare against. More precisely, a query set computed by the algorithm must reveal sufficient information to identify an approximate knapsack solution, while the optimal query set we compare against has to reveal sufficient information to identify an optimal solution. We show that this resource-augmented setting allows interesting non-trivial algorithmic results.