Лаборатория сложности / Диагонализация SAT
P != NP как вопрос сжатия, пространства свидетелей и самореференции
В этом зале загруженная серия препринтов реконструируется как академическая рабочая модель: предложенный путь доказательства через несжимаемость пространства решений SAT, а не заявление о признании устоявшимся сообществом.
Независимый препринт Требуется экспертиза Шесть загруженных PDF-файлов
предположим, что f фи_ф исключить f(enc(phi_f)) САТ остался?
Проблема
P против NP кадра
Если SAT разрешима за полиномиальное время, то P = NP; если такой процедуры с полиномиальным временем не существует, P != NP.
Формальный объект
P = NP iff SAT in P Функция в аргументе
Устанавливает целевую задачу посредством стандартной эквивалентности Кука-Левина.
стандартный фонИнтерактивный инструмент
Сжать пространство-свидетель, а затем посмотреть, как диагональная формула избегает его.
Эта конечная модель демонстрирует механизм загрузки документов: выбирается небольшой список кандидатов, формула добавляет одно условие исключения для каждого кандидата, а оставшийся логический куб проверяется на наличие свидетелей. Он визуализирует шаг диагонального исключения; полный препринт дополнительно требует аргументов с фиксированной точкой, конструктивности и барьера.
Режим верификатор игрушек Показывает логику построения; это не заменяет полное доказательство.
Булев куб 16 заданий
Остальные свидетели 11
Сгенерированная формула
phi_f исключает именно набор кандидатов
Компрессор выбрал пять назначений. Сгенерированный CNF запрещает эти пять пунктов и оставляет другие назначения доступными в качестве свидетелей.
кандидат f исключен phi_f оставшийся удовлетворительный свидетель первый доступный свидетель
Обзор кабины
Версия мирового уровня должна раскрывать обязательства по доказательству, а не скрывать их.
Выбранный узел аудита 01
Эквивалентность сжимаемости
Что демонстрирует эта страница
Страница моделирует компрессор как конечный селектор кандидатов по {0,1}^n.
Что должен доказать PDF-файл
Докажите точную эквивалентность полиномиального компрессора набора попаданий для свидетелей SAT и процедуры решения/поиска SAT с полиномиальным временем.
Режим отказа, который следует исключить
Если CH слабее или сильнее, чем P = NP, диагональное противоречие может не соответствовать целевой теореме.
Статус Обзор цели
Загруженный корпус P != NP
Шесть документов рассматриваются как одна проверяемая система аргументов.
Часть I 7 страниц
Опровержение гипотезы сжимаемости.
Определяет CH для SAT и вводит диагональную самореферентную формулу phi_f.
- Вклад
- Фреймы P != NP как отказ универсального компрессора пространства решений полиномиального размера.
- Обзор позы
- Представлено на сайте как самостоятельный препринт, предлагающий доказательство.
Часть II 7 страниц
Полиномиальная конструкция и барьеры
Заменяет использование теоремы о неподвижной точке явной программой построения полинома.
- Вклад
- Перемещает аргумент от абстрактной ссылки на себя к конструктивному алгоритмическому объекту.
- Обзор позы
- Утверждение о полиномиальной конструктивности остается ключевым объектом проверки.
Часть III 8 страниц
Практическая проверка и специфика
Добавляет вычислительные проверки в стиле PySAT и сравнивает поведение с 2SAT.
- Вклад
- Вводит эмпирический уровень выполнимости, исключения и NP-полной специфичности.
- Обзор позы
- Эксперименты иллюстрируют конструкцию; они не заменяют формального доказательства.
Часть IV 9 страниц
Формализация и исчерпывающая валидация
Повторно формулирует CH, сходимость с фиксированной точкой, выполнимость, исключение и крайние случаи.
- Вклад
- Собирает обязательства по доказательству в более подробный контрольный список.
- Обзор позы
- Сайт оставляет их в качестве обязательств для независимой математической проверки.
Часть V 8 страниц
Доказательство эквивалентности, закрытие пробелов, анализ барьеров
Усиливает эквивалентность между CH и P = NP и устраняет пробелы в обзорах.
- Вклад
- Превращает последовательность в единый контрольный журнал: эквивалентность, построение, исключение, барьеры.
- Обзор позы
- Утверждения представлены как авторская архитектура препринта, а не как доказанная теорема.
Расширенная часть V 106 страниц
Теорема о росте меры и устойчивость барьеров
Развивает структурную диагонализацию, синтаксический гаджет и инвариант меры роста.
- Вклад
- Добавляет большую методологическую защиту от релятивизации, естественных доказательств и алгебризации.
- Обзор позы
- Лучше всего рассматривать его как основное проверочное досье для экспертов.
Разобранный корпус/слой доказательств
Серия PDF теперь рассматривается как структурированное досье с доказательствами.
Шесть загруженных PDF-файлов были извлечены в текст и проанализированы как один связанный аргумент: сжатие SAT, полиномиальная самореференция, диагональное исключение, устойчивость к барьерам и формальные цели проверки. Этот блок отделяет публичное заявление от обязательств по точному доказательству, которые эксперт-рецензент должен проверить в первую очередь.
Стандартизируйте гипотезу
Объедините CH / IH / CH1 в одно точное утверждение: компрессор набора кандидатов-свидетелей SAT с полиномиальным временем, выходные данные которого пересекают удовлетворяющие назначения каждого выполнимого CNF.
Докажите эквивалентность P = NP
Покажите оба направления: SAT в P дает компрессору самосокращение поиска, а компрессор решает SAT, проверяя свой выходной список полиномиального размера.
Сделать phi_f конструктивным
Самореферентная формула должна быть получена путем явной конструкции за полиномиальное время, а не путем неформального обращения к интуиции с фиксированной точкой.
Сохранить выполнимость
Диагональные предложения должны исключать кандидатов, возвращаемых f, оставляя при этом хотя бы одного удовлетворительного свидетеля после всех ограничений кодирования и гаджетов.
Изолировать границу 2SAT
Конструкция должна быть представлена как механизм SAT/3SAT; 2SAT следует рассматривать как граничный случай, а не как доказательство того, что известные P-задачи парадоксальны.
Держите эксперименты в своей полосе
Трассировки PySAT и конечное моделирование являются ценными артефактами воспроизводимости, но асимптотическое разделение должно опираться на формальную конструкцию.
Корпусные файлы
Откройте извлеченный текст и карту обзора.
Эти файлы делают корпус доказательств проверяемым. Анализ Markdown фиксирует архитектуру аргументов, сильные стороны, вероятные возражения экспертов и следующую формальную работу, необходимую перед презентацией коллегам.
Обязательства по доказательству
Сайт должен сделать аргументы понятными, а не просто впечатляющими.
Самая сильная версия этой страницы — это панель проверки: каждое важное утверждение становится узлом, каждый узел имеет формулу, а каждая формула содержит вопрос аудита.
- CH-эквивалентность P = NP устанавливается с помощью явной функции набора кандидатов.
- phi_f должен быть конструктивным в полиномиальных пределах для любого допустимого f.
- Исключающие дизъюнкты должны запрещать кандидатов функции f, не нарушая выполнимость.
- Запас выполнимости должен выдерживать накладные расходы на кодирование и граничные случаи.
- Аргумент не должен быть замаскированным релятивизирующим, натурализующим или алгебраизирующим методом.
- Эмпирические проверки следует рассматривать как свидетельство воспроизводимости, а не как окончательное доказательство.
Ссылка на общедоступное досье
Как работа на сайте остается академически осторожной
Карта SSRN: препринт опубликован 6 мая 2025 г. и исправлен 7 мая 2025 г., в нем представлены архивные аргументы по поводу SAT, формальной сложности и сжимаемости.
Открытое официальное досьеСвязь между поиском решения и проверкой решения
Пространства решений SAT и можно ли сжать их структуру
Диагонализация и несжимаемость рассматриваются как точки давления.
Отображается как формальная карта пределов, а не как непроверенная окончательная теорема.