Max Home Industry• Формат числа 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