Какой вопрос решают
Предметы рациональных размеров надо уложить в контейнеры вместимости 1. Дробная линейная программа разрешает купить долю конфигурации. Насколько её ответ может отличаться от реального числа контейнеров?
Для каждого фиксированного целого c≥0 заявлены примеры с целым значением конфигурационной LP B, но оптимумом больше B+c. Отдельно заявлена NP-трудность различения упаковки в B контейнеров и невозможности упаковки в B+c.
Почему выбрано: Показывает практическую ценность запрета: он помогает не обещать продукту недостижимую универсальную точность.
До и после
Введение отличает аддитивный разрыв от известных мультипликативных/асимптотических приближений. Результат не опровергает полезность LP и не утверждает большой относительный разрыв. Из «для любого c есть пример» не следует конкретная логарифмическая скорость роста разрыва по длине входа.
Это сопоставление по введению рукописи. Независимый исчерпывающий обзор приоритета не выполнен.
Точное утверждение и условия
118-01, теоремы 1.2 и 1.3, PDF с. 2. Все размеры в конструкции >1/6. На построенных примерах совпадают дробные оптимумы вариантов LP по типам предметов и по индивидуальным копиям. Неограниченный аддитивный разрыв — безусловное утверждение конструкции; невозможность эффективного алгоритма с таким обещанием требует предположения P≠NP.
Источник: указанные теоремы в локальных PDF ниже. Формулировка пересказана, но ключевые кванторы, модель и оговорки сохранены.
Три уровня объяснения
Следующие аналогии и объяснения — наша интерпретация, не дополнительные теоремы.
Архитектура доказательства
Пересказ вводного обзора, а не построчная проверка доказательства.
Построить комбинаторный гаджет покрытия с интервалами и квотами.
Закодировать его рациональными размерами, контролируя все конфигурации, а не только предложенный дробный носитель.
Из любой почти оптимальной целочисленной упаковки извлечь допустимое покрытие; отдельно предъявить дробное решение стоимости B.
Что известно о проверке
Наличие scope notes — свидетельство заявленного охвата, а не проведённой здесь проверки редукции и битовых размеров. Исполняемого Lean-кода нет.
Читать локальное описание формального охвата
Наличие PDF, извлечение текста, успешный маленький эксперимент и внешний результат-предшественник — разные виды свидетельств. Ни один из них здесь не отмечен как независимое подтверждение всей новой теоремы.
Практика: наш вывод, не обещание автора
Аудитор разрыва LP и реального решения: сообщать оператору нижнюю границу, лучший найденный план и непокрытый разрыв, а не выдавать дробный ответ за исполнимый. Это использование ограничения, не новый решатель упаковки.
Ограничения переноса
Синтетические примеры могут иметь огромные размеры записи. Реальные коробки часто многомерны, с весом и несовместимостями; данная теорема одномерна. Отрицательный результат не даёт SLA для эвристики.
Планы проверки: Аудитор разрыва между LP и упаковкой.
Исходники и реальный охват чтения
Номера страниц относятся к физическим страницам PDF, начиная с 1. Ссылки на GitHub не закреплены на текущем commit; воспроизводимый источник — локальный путь и SHA-256.
118-01 · Additive hardness and unbounded configuration gaps in bin packing
Реальный охват: Просмотрены PDF с. 1–4: Модели LP, две главные теоремы, начальный план редукции. Полный объём PDF: 26 с.
math_sources/math_research_07_of_08/preprints/Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026/Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026.pdfSHA-256: cf1e9b383ad38a1c6b8d0117e1e6f485a482480d05471d11de02c81020cbb9e6Каталог: context/CONTENTS.md, строка 2913. Путь и хеш относятся к загруженной версии.
Семейство в CONTENTS.md, строка 2906. Структурированные заметки · Журнал внешней сверки.