Булева проблема пифагоровых троек
Булева проблема пифагоровых троек — одна из задач теории Рамсея.
Формулировка[править | править код]
Можно ли разделить множество натуральных чисел на две части таким образом, чтобы каждая часть не имела ни одной пифагоровой тройки?
Замечание[править | править код]
В терминах покраски чисел проблема выглядит так: можно ли раскрасить натуральные числа в два цвета так, чтобы ни одна пифагорова тройка не была монохромной?
История[править | править код]
В 2015 году Джошуа Купер и Ральф Оверстрит раскрасили двумя цветами 7664 натуральных чисел так, что все пифагоровы тройки были разноцветными[1].
Марин Гейле, Оливер Кульман и Виктор Марек в мае 2016 года решили задачу. Они доказали, что множество натуральных чисел {1,…, 7824} можно поделить так, чтобы каждая часть не имела ни одной пифагоровой тройки, но это невозможно для {1,…, 7825}[2].
Теорема была доказана путём перебора всех вариантов с использованием 800 ядер суперкомпьютера Stampede в Компьютерном центре Техасского университета в течение двух дней. Размер файла с доказательством в формате DRAT достиг 200 терабайт. Из него был изготовлен и помещён в архив сертификат размером 68 гигабайт. Для 7824 натуральных чисел существует несколько решений проблемы, но для 7825 решений не найдено[3].
Статья Марин Гейле, Оливера Кульмана и Виктора Марека была выбрана для доклада на конференции SAT 2016, которая состоялась в Бордо (Франция) в июле 2016 года, и была признана лучшей работой[4][5].
См. также[править | править код]
- Теорема Рамсея
- Задача выполнимости булевых формул (SAT)
- Гипотеза Эрдёша — Секереша о выпуклых многоугольниках
Примечания[править | править код]
- ↑ Joshua Cooper, Ralph Overstreet (2015).
- ↑ Heule, Marijn J. H.; Kullmann, Oliver; Marek, Victor W. (2016-05-03). "Solving and Verifying the Boolean Pythagorean Triples problem via Cube-and-Conquer". arXiv:1605.00723.
- ↑ Introduction for the general public. Дата обращения: 3 сентября 2016. Архивировано 30 августа 2016 года.
- ↑ "Theory and Applications of Satisfiability Testing – SAT 2016" (PDF). Theory and Applications of Satisfiability Testing – SAT 2016. doi:10.1007/978-3-319-40970-2_15. Архивировано из оригинала (PDF) 22 сентября 2016. Дата обращения: 31 августа 2016.
{{cite conference}}: Неизвестный параметр|booktitle=игнорируется (|book-title=предлагается) (справка) - ↑ Theory and Applications of Satisfiability Testing – SAT 2016. Дата обращения: 3 сентября 2016. Архивировано 25 августа 2016 года.