Какой вопрос решают
Нужно хранить строки так, чтобы каждая встречалась внутри одной общей строки. Например, CAT, ATG и TGA можно перекрыть. Как сделать общую запись короткой, сохранив все подстроки?
Заявлен детерминированный полиномиальный алгоритм с длиной не более 2·OPT для произвольного конечного набора явно записанных строк.
Почему выбрано: Близко к программной реализации, есть ясный baseline и проверяемый маленький оптимум.
До и после
В независимом препринте Chukhin и соавторов заявлено 7/3 для общего SCS и 3 для Greedy; в препринте Shibata — нижняя граница 9/4 для Greedy. Просмотрены их формулировки, не проведён аудит доказательств. Это первичные предшественники, а не независимая проверка работы 128. Историческая граница 2023 года 2,466 не должна называться самой новой.
Внешние первичные источники: Chukhin, Kulikov, Mihajlin, Smal — A Tight Cycle-Cover Inequality for Shortest Common Superstring · Shibata — Disproving the Greedy Superstring Conjecture · Englert, Matsakis, Veselý — ISAAC 2023, статья 29.
Точное утверждение и условия
128-01, теорема 1.1, PDF с. 1: конечный явный вход, алфавит входит в кодирование, учитывается полная битовая длина. Результат T содержит каждую исходную строку и удовлетворяет |T|≤2·OPT. Гарантия относится к новому иерархическому алгоритму, не к правилу максимального перекрытия.
Источник: указанные теоремы в локальных PDF ниже. Формулировка пересказана, но ключевые кванторы, модель и оговорки сохранены.
Три уровня объяснения
Следующие аналогии и объяснения — наша интерпретация, не дополнительные теоремы.
Загрузка локального эксперимента…
Архитектура доказательства
Пересказ вводного обзора, а не построчная проверка доказательства.
Доказать нижнюю границу обязательных вхождений, учитывая не только минимальные периоды.
Построить сбалансированный, возможно несвязный, граф стоимости W.
Иерархически соединить компоненты с контролем периодических циклов и получить стоимость ≤2W≤2OPT.
Что известно о проверке
Scope notes связывают формализацию с заявленной гарантией. Исходники и исполнение отсутствуют; приведённая схема не проверяет оценку W и стоимость соединений.
Читать локальное описание формального охвата
Наличие PDF, извлечение текста, успешный маленький эксперимент и внешний результат-предшественник — разные виды свидетельств. Ни один из них здесь не отмечен как независимое подтверждение всей новой теоремы.
Практика: наш вывод, не обещание автора
Стенд компоновки строковых пулов: exact DP на малых наборах, Greedy как базовый метод, размеры и время. Новый двухкратный алгоритм — отдельный исследовательский модуль после проверки, не подпись к обычной жадной демонстрации.
Ограничения переноса
SCS не заменяет универсальное сжатие; метаданные и индексы тоже занимают место. Модель не учитывает ошибки чтения и неоднозначность реального генома. Худшая гарантия не обещает улучшения над Greedy на вашем корпусе.
Планы проверки: Лаборатория компоновки строковых пулов.
Исходники и реальный охват чтения
Номера страниц относятся к физическим страницам PDF, начиная с 1. Ссылки на GitHub не закреплены на текущем commit; воспроизводимый источник — локальный путь и SHA-256.
128-01 · A Polynomial-Time 2-Approximation for Shortest Common Superstring
Реальный охват: Просмотрены PDF с. 1–4: Теорема, предшественники, графовая конструкция и начало леммы о вхождениях. Полный объём PDF: 19 с.
math_sources/math_research_07_of_08/preprints/A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026/paper.pdfSHA-256: 45ef658ae322212b4c83626fd2bfa0ad8e459f6564b4bd0395e0c9ee8eb30dfeКаталог: context/CONTENTS.md, строка 3093. Путь и хеш относятся к загруженной версии.
Семейство в CONTENTS.md, строка 3086. Структурированные заметки · Журнал внешней сверки.