// Без комментариев — Unums, головоломки 1 × n сложны & P? = NP


• Формат числа Unum: математические основы, реализация и сравнение с числами с плавающей запятой IEEE 754

• Даже пазлы размером 1 × n и головоломки действительно сложны

• П ? = NP

Иногда новости достаточно хорошо сообщаются в других местах, и нам нечего добавить, кроме как обратить на это ваше внимание.

Без комментариев — это формат, в котором мы представляем исходную информацию об источнике, слегка отредактированную, чтобы вы могли решить, хотите ли вы следить за ней.

Формат числа Unum: математические основы, реализация и сравнение с числами с плавающей запятой IEEE 754

Возможно, вы помните формат Unum, о котором сообщалось еще в мае 2016 года в книге Better Than Floating — New Number Format Avoids Avoids, и теперь у нас есть статья, в которой сравнивается формат с более стандартным форматом IEE 754:

В этой диссертации исследуется современная концепция машинных чисел, основанная на интервальной арифметике под названием «Unums», и сравнивается ее с арифметикой с плавающей запятой IEEE 754, оцениваются возможные варианты использования этого формата там, где числа с плавающей запятой неадекватны. В ходе этого экзамена эта диссертация строит теоретические основы для чисел с плавающей запятой IEEE 754, интервальной арифметики, основанной на проективно расширенных действительных числах и Unums.

На самом деле нет вывода:

В конце концов, все сводится к вопросу, лучше ли использование двух 32-битных чисел с плавающей запятой IEEE 754 для моделирования такого замкнутого интервала, чем использование одного 64-битного числа с плавающей запятой IEEE 754 для разнообразного набора алгоритмов. Стратегия поиска решения путем перехода от грубой сетки к мелкой для Unums может быть легко реализована с помощью ограниченных закрытых интервалов с плавающей запятой, а также может оказаться полезной для определенных приложений.

Даже головоломки размером 1 × n и головоломки действительно сложны

Часто задаваемый вопрос о сложных проблемах заключается в том, насколько легко вы должны их решить, прежде чем они действительно станут легкими. Последний сюрприз заключается в том, что даже «легкие» пазлы сложны:

Мы доказываем вычислительную сложность вращения и размещения n квадратных плиток в массиве 1 × n таким образом, чтобы соседние плитки были совместимы — либо равные цвета краев, как в головоломках с сопоставлением краев, либо соответствующие формы вкладок / карманов, как в головоломках.

Помимо базовой NP-жесткости, мы доказываем, что NP-сложно даже приблизительно максимизировать количество размещенных плиток (допуская пустые плитки), при соблюдении ограничения совместимости между непустыми плитками с коэффициентом 0,9999999851. (С другой стороны, есть простое 12-приближение.)

Это первое (правильное) доказательство несовместимости ребер и головоломок. Попутно мы доказываем NP-трудность различения для ориентированного графа на n узлах между имеющимся гамильтоновым путем (длина n − 1) и наличием не более чем 0,999999284 (n − 1) ребер, которые образуют непересекающееся по вершинам объединение пути. Мы используем эту жесткость зазора и сокращения, сохраняющие зазор, чтобы установить аналогичную жесткость зазора для головоломки 1 × n и головоломок с подгонкой краев.

Если вы не уверены, что такое головоломка с сопоставлением краев, вам поможет следующий рисунок, взятый из бумаги:

В документе также упоминается:

Недавняя популярная (без подписи) головоломка с сопоставлением краев — Eternity II, за первый решатель которой (до 2011 года) был разыгран приз в размере 2 000 000 долларов США. Загадка остается нерешенной (за исключением, по-видимому, ее создателя Кристофера Монктона). Лучшее частичное решение на сегодняшний день либо размещает 247 из 256 частей без ошибок, либо размещает все 256 частей, правильно сопоставляя 467 из 480 ребер.

П ? = NP

Самым важным вопросом вычислительной теории в настоящее время является проблема P = NP. От этого зависит безопасность большинства наших цифровых транзакций, не говоря уже о множестве других вопросов теории сложности. Любимый теоретик сложности программистов Скотт Ааронсон только что опубликовал обновленный и очень читаемый обзор того, где стоит проблема в целом:

В 1955 году Джон Нэш направил в Агентство национальной безопасности замечательное письмо, в котором, стремясь создать теоретические основы криптографии, он почти сформулировал то, что сегодня мы называем проблемой P? = NP, которая считается одной из величайших открытых проблем науки. .

Здесь я делаю обзор состояния этой проблемы в 2017 году для широкого круга математиков, ученых и инженеров. Я предлагаю личный взгляд на то, о чем идет речь, почему это важно, почему разумно предположить, что P ̸ = NP одновременно истинно и доказуемо, почему доказать это так сложно, ландшафт связанных проблем и, что особенно важно, какой прогресс был достигнут. сделано за последние полвека для решения этих проблем. Обсуждение прогресса включает диагонализацию и нижние границы схемы; барьеры релятивизации, алгебризации и естественных доказательств; и недавние работы Райана Уильямса и Кетана Малмули, которые (по-разному) намекают на двойственность между доказательствами невозможности и алгоритмами.

Если у вас есть какие-то умные / сумасшедшие теории, которые доказывают, что P = NP, то вам, по крайней мере, нужно прочитать и понять все 116 страниц, прежде чем вы что-то скажете миру. Конечно. если у вас есть практический способ уменьшить проблемы NP до P, тогда. лично. Я бы ничего не сказал и продолжал наслаждаться вновь обретенной свободой, прежде чем кто-то другой обнаружит то же самое.

Если вы хотите получить некоторую предысторию того, как был написан опрос, прочтите: Моя 116-страничная статья об обзоре P vs. NP: лучше поздно, чем никогда

Чтобы быть в курсе новых статей на I Programmer, подпишитесь на нашу еженедельную рассылку новостей, подпишитесь на RSS-канал и подпишитесь на нас в Twitter, Facebook, Google+ или Linkedin.

Комментарии

Оставьте комментарий или просмотрите существующие комментарии с помощью Disqus


Добавить комментарий