stringtranslate.com

Марийн Хеуле

Мариенус Йоханнес Хендрикус Хойле (родился 12 марта 1979 года в Рейнсбурге , Нидерланды ) [1] [2] — голландский учёный-компьютерщик из Университета Карнеги-Меллона , изучающий решатели SAT . Хойле использовал эти решатели для решения математических гипотез, таких как задача о булевых пифагорейских тройках , теорема Шура № 5 и гипотеза Келлера в размерности семь.

Карьера

Хойл получил докторскую степень в Делфтском технологическом университете в Нидерландах в 2008 году. Он был научным сотрудником, а затем доцентом Техасского университета в Остине с 2012 по 2019 год. С 2019 года он является доцентом кафедры компьютерных наук в Университете Карнеги-Меллона . [2]

Визуализация решения задачи Пифагоровых троек

В мае 2016 года он вместе с Оливером Кульманном и Виктором В. Мареком использовал решение SAT для решения задачи о булевых пифагорейских тройках . [3] [4] Утверждение теоремы, которую они доказали, следующее:

Теорема  —  Множество {1, . . . , 7824} можно разбить на две части так, что ни одна часть не содержит пифагорову тройку, тогда как для {1, . . . , 7825} это невозможно. [5]

Чтобы доказать эту теорему, возможные раскраски {1, ..., 7825} были разделены на триллион подслучаев с использованием эвристики . Затем каждый подкласс был решен решателем булевой выполнимости . Создание доказательства заняло около 4 CPU-лет вычислений в течение двух дней на суперкомпьютере Stampede в Техасском передовом вычислительном центре и сгенерировало 200-терабайтное пропозициональное доказательство (которое было сжато до 68 гигабайт в виде списка используемых подслучаев). [5] Статья, описывающая доказательство, была опубликована на конференции SAT 2016, [5] где она получила награду за лучшую статью. [5] Премия в 100 долларов, которую Рональд Грэм первоначально предложил за решение этой проблемы в 1980-х годах, была присуждена Хейлу. [3]

Он использовал решение SAT, чтобы доказать, что число Шура 5 равно 160 в 2017 году. [4] [6] Он доказал гипотезу Келлера в размерности семь в 2020 году. [7]

В 2018 году Хейл и Скотт Ааронсон получили финансирование от Национального научного фонда для применения решения SAT к гипотезе Коллатца . [7]

В 2023 году совместно с Суберкасо он доказал, что упаковочное хроматическое число бесконечной квадратной сетки равно 15 [8] [9]

Смотрите также

Ссылки

  1. ↑ Calmthout, Мартейн ван (6 июня 2016 г.). «Bewijs dat net op 200 прошлых ноутбуков» (PDF) . де Фолькскрант (на голландском языке). п. 23. Архивировано (PDF) из оригинала 5 января 2022 года . Проверено 11 мая 2021 г.
  2. ↑ Аб Хойле, Марин (20 августа 2019 г.). «Марейн Дж. Х. Хойле» (PDF) . www.cs.cmu.edu . Проверено 15 июня 2021 г.
  3. ^ ab Lamb, Evelyn (26 мая 2016 г.). «Двухсоттерабайтное математическое доказательство — самое большое из когда-либо существовавших». Nature . 534 (7605): 17–18. Bibcode :2016Natur.534...17L. doi : 10.1038/nature.2016.19990 . PMID  27251254.
  4. ^ ab Hartnett, Kevin. «Computer Scientists Attempt to Corner the Collatz Conjecture» (Ученые-компьютерщики пытаются загнать в угол гипотезу Коллатца). Журнал Quanta . Получено 8 марта 2021 г.
  5. ^ abcd Heule, Marijn JH; Kullmann, Oliver; Marek, Victor W. (2016). «Решение и проверка задачи Boolean Pythagorean Triples с помощью Cube-and-Conquer». В Creignou, Nadia; Le Berre, Daniel (ред.). Theory and Applications of Satisfiability Testing – SAT 2016: 19-я международная конференция, Бордо, Франция, 5–8 июля 2016 г., Труды . Lecture Notes in Computer Science. Vol. 9710. pp. 228–245. arXiv : 1605.00723 . doi :10.1007/978-3-319-40970-2_15.
  6. ^ Хойле, Марин Дж. Х. (2017). «Шур номер пять». arXiv : 1711.08076 [cs.LO].
  7. ^ ab Hartnett, Kevin. «Компьютерный поиск решает 90-летнюю математическую задачу». Quanta Magazine . Получено 8 марта 2021 г.
  8. ^ Subercaseaux, Bernardo; Heule, Marijn JH (23 января 2023 г.). «Упаковочное хроматическое число бесконечной квадратной сетки равно 15». arXiv : 2301.09757 [cs.DM].
  9. ^ Хартнетт, Кевин (20 апреля 2023 г.). «Число 15 описывает секретный предел бесконечной сетки». Журнал Quanta . Получено 20 апреля 2023 г.

Внешние ссылки