OAI.BinPackingGap.main_results

The theorem states four results for bin packing with rational item sizes in (0,1], unit bin capacities, and optimum opt(I), the minimum number of bins needed. First, for every nonnegative integer c there are an instance I and a nonnegative integer B with exactly 5B items, all sizes strictly between 1/6 and 1, such that opt(I)>B+c while both configuration linear programming values equal B. The individual-item value is the infimum of total nonnegative weights on feasible subsets of items, with each item covered to weight at least one; the size-type value uses feasible multisets of the distinct sizes and covers each size to at least its multiplicity. Second, for every c and every language L in NP, there is a polynomial-time reduction mapping each bit string x to B and a valid rational instance of 5B items, all larger than 1/6, such that membership in L implies a packing in B bins, whereas nonmembership excludes every packing in B+c bins. Third, a polynomial-time algorithm returning, on every valid encoded instance, a feasible packing using at most opt(I)+c bins for some fixed nonnegative integer c exists if and only if P=NP. Fourth, if P=NP, there is such an algorithm with c=0 that returns an optimal packing on every valid instance, returns the zero-bin empty packing on the empty instance, and rejects both undecodable bit strings and encodings of invalid instances. Here valid raw instances are lists of numerator-denominator pairs (a,b) satisfying 0<a≤b; computation uses the specified binary encodings and finite-alphabet Turing machines, and NP means polynomially bounded certificates verifiable in polynomial time.