Автор: WinAx

Вселенную можно рассматривать как огромный физический компьютер, на котором работает 13,7 миллиарда человек. Результат его программы — такой, какой он есть. Обладает ли вселенная необходимой мощностью или ей нужны хитроумные алгоритмы?

Меня всегда поражает тонкость вероятности. Вы можете процитировать проблему Монти Холла или проблему Фишера Йейтса, но как насчет проблемы с кузнечиком? Легко сформулировать, но очень сложно решить и немного невероятно.

Это умная идея, которая кажется очевидной только после того, как вы ее увидели. Есть ли другие приложения, которые ждут, чтобы их придумали?

Одно дело знать, что что-то маловероятное является полным по Тьюрингу; совсем другое — использовать его для создания компьютера, а затем реализовать что-то реальное. Именно это и произошло с «Game Of Life» Конвея, когда был сконструирован компьютер для игры в тетрис. Это замечательное достижение, которое должно поставить ваш мозг в штопор.

Доказательств того, что P=NP, и даже для менее интересного и более вероятного P≠NP, очень много. Большинство из них принадлежит энтузиастам, которых, как правило, можно похвалить за энтузиазм, но не за доказательства. Однако последнее доказательство принадлежит уважаемому теоретику сложности и не может быть отвергнуто обычным способом. Последнее обновление: статья отозвана.

Проблема размещения восьми ферзей на шахматной доске, чтобы ни один ферзь не атаковал другого, является решенной задачей, как и размещение n ферзей на доске размером nxn. Однако, если вы поместите несколько ферзей на доску и попросите завершить, тогда проблема будет NP завершена.

Мы широко используем алгоритмы сжатия, чтобы сэкономить как хранилище, так и время. Наиболее популярные алгоритмы основаны на сжатии словаря LZ и используются в форматах GIF, Deflate, Zip, PNG. Его даже назвали вехой IEEE. Но мы мало о них знаем. Один давний вопрос: может ли добавление одного бита в файл кардинально изменить достигнутую степень сжатия? Конечно […]

Если вам сложно собрать кубик Рубика, вам будет приятно узнать, что это действительно так. Теперь доказано, что определение разрешимости случайного куба ровно за n ходов является NP полным.

Числовой формат с плавающей запятой используется для большинства вычислений, и мы склонны доверять ему, но это доверие неуместно. Вычисления с плавающей запятой могут быть настолько ошибочными, что напоминают шум. Теперь есть способ автоматически определять, когда что-то идет не так.

Сможет ли человек пережить нападение льва двух львов? Да, если речь идет о математике, а не о настоящих львах. Это почти классическая математическая головоломка.