Какой вопрос решают
Есть зависимости между работами, каждая занимает один такт. Можно ли закончить их к сроку T на трёх одинаковых машинах, не прерывая задачи? Реальные проекты обычно имеют неодинаковые длительности — это уже вне данной постановки.
Для явно заданного ациклического графа зависимостей заявлен точный полиномиальный алгоритм оптимального расписания на трёх машинах.
Почему выбрано: Ясный пример фундаментальной алгоритмической ценности без немедленного коммерческого эффекта.
До и после
Введение приводит специальные структуры зависимостей, субэкспоненциальные точные методы и квазиполиномиальные схемы приближения. Новизна заявлена в классе сложности точного решения общей модели с тремя машинами, а не в превосходстве над этими методами на конечных входах.
Это сопоставление по введению рукописи. Независимый исчерпывающий обзор приоритета не выполнен.
Точное утверждение и условия
124-01, теорема 1.1, PDF с. 2: n≥1 единичных неперерываемых задач, три идентичные машины; для целого 1≤T≤n решается выполнимость и строится расписание, а также находится минимальный makespan. Битовая сложность на многоленточной машине Тьюринга O((L+2)^150020). Нет времён поступления, задержек связи, ограничений пригодности машины и дополнительных ресурсов.
Источник: указанные теоремы в локальных PDF ниже. Формулировка пересказана, но ключевые кванторы, модель и оговорки сохранены.
Три уровня объяснения
Следующие аналогии и объяснения — наша интерпретация, не дополнительные теоремы.
Загрузка локального эксперимента…
Архитектура доказательства
Пересказ вводного обзора, а не построчная проверка доказательства.
Нормализовать полные расписания и разбиение на промежутки.
Доказать существование ограниченных глобальных описаний нужных множеств работ с помощью перестановок рамок и ранговых условий.
Перебрать ограниченные формулы и собрать динамическую программу. Большой предел размера описания приводит к степени 150020.
Что известно о проверке
Заявленный охват в scope notes не даёт здесь независимо проверенного конечного алгоритма. Критическое соответствие между существованием компактного свидетельства и его эффективным перечислением не воспроизведено.
Читать локальное описание формального охвата
Наличие PDF, извлечение текста, успешный маленький эксперимент и внешний результат-предшественник — разные виды свидетельств. Ни один из них здесь не отмечен как независимое подтверждение всей новой теоремы.
Практика: наш вывод, не обещание автора
Полезно для исследования границы трудности и поиска упрощений структурной леммы. Браузерная демонстрация использует старую экспоненциальную динамику по подмножествам, не этот полиномиальный алгоритм.
Ограничения переноса
Даже грубая оценка при L=10 имеет десятки тысяч десятичных разрядов. Никаких данных о реальном ускорении нет. Не переносится на произвольные длительности, четыре машины или производственные ограничения.
Исходники и реальный охват чтения
Номера страниц относятся к физическим страницам PDF, начиная с 1. Ссылки на GitHub не закреплены на текущем commit; воспроизводимый источник — локальный путь и SHA-256.
124-01 · A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling
Реальный охват: Просмотрены PDF с. 1–4: Постановка, теорема и описание ограниченных формул. Полный объём PDF: 22 с.
math_sources/math_research_07_of_08/preprints/A-polynomial-time-algorithm-for-three-machine-unit-job-scheduling-September-24-2026/paper.pdfSHA-256: 2080c4ad5953f225c1db7fe803c6d8602ae499510719cfe0cb4f22f99bccff1eКаталог: context/CONTENTS.md, строка 3020. Путь и хеш относятся к загруженной версии.
Семейство в CONTENTS.md, строка 3013. Структурированные заметки · Журнал внешней сверки.