8 problems

Consider unrestricted multi-way partitioning: divide $\{X_1,\ldots,X_n\}$ into $q$ subsets so that their sums are as equal as possible, without requiring every subset to have cardi…

Let the costs of two partitions be represented by spin configurations, and consider configurations associated with nearby fixed typical energies. Typical-energy overlap conjecture.…

Represent partitions by spin configurations and associate overlaps to pairs of configurations corresponding to nearby energy levels. Overlap part of the local REM conjecture. The c…

Let the energies of a number-partitioning model be ordered increasingly, and consider the energy levels near a fixed energy. Local REM conjecture. The local energy spectrum should…

Polynomial-time indistinguishability conjecture. Fix any $c>1$. There exists no polynomial-time algorithm that distinguishes the p-texttt{NPP} from the u-texttt{NPP} with probabili…

Computational indistinguishability conjecture. While the two versions are statistically distinguishable, it is impossible to distinguish them in polynomial time with non-trivial er…

Number-partitioning hardness conjecture. The problem is algorithmically hard for objective values smaller than order

Asymptotic-equivalence conjecture. The error introduced by approximating the exact recursion by the rate equation vanishes as $n\to\infty$; equivalently, the rate equation and the…