Рубрика «NP-полная задача»

Есть проблемы гораздо сложнее, чем NP-Complete - 1

Люди часто сравнивают P и NP в таком духе, что проблемы P простые, а NP — сложные. Но это чрезмерное упрощение. На самом деле проблемы могут быть намного, намного сложнее, чем NP.

В этом смысле можно вспомнить интеллектуально-фантастический триллер Travelling Salesman (Коммивояжёр, 2012) о четырёх математиках, нанятых правительством США для решения самой сложной проблемы в истории информатики — равенства классов сложности P и NP (P versus NP problem). И им это удалось. Чиновник министерства обороны США предлагает за их алгоритм вознаграждение $10 млн. Но сами математики слишком хорошо понимают, какие разрушительные последствия принесёт в мир их открытие. Один из лучших фильмов про математику в истории кинематографа…
Читать полностью »

Задачу о N ферзях признали NP-полной задачей - 1
Первый вариант головоломки 1850 года, когда два ферзя заранее установлены на доску, а игрок должен расставить остальных ферзей (два решения задачи см. под катом)

Задача о N ферзях состоит в том, чтобы разместить N ферзей на доске размером N×N таким образом, чтобы ни один ферзь не находился под боем другого, при этом на доске заранее установлены несколько ферзей. То есть в итоге никакие два ферзя не должны находиться на одной линии или диагонали. Впервые задачку сформулировали в 1848 году, а в 1850 году придумали вариант головоломки, когда некоторое количество ферзей заранее поставлено на доску, а игрок должен расставить остальных, если это возможно.

Исследователи из Сент-Эндрюсского университета (Шотландия) опубликовали научную статью, в которой доказывают, что задача о N ферзях является не только #P-полной задачей, но также NP-полной задачей. Более того, Математический институт Клэя (США) готов заплатить миллион долларов любому, кто сможет оптимизировать решение этой задачи как задачи на доказательство P=NP.
Читать полностью »

image

Известно, что на старых картах, на неизведанных территориях, часто помещали зловещее предупреждение: «Здесь живут драконы». Вероятно, смысл этого предупреждения состоял в том, что не стоит входить в это пространство мира, не будучи готовыми сражаться с внушающим ужас противником. Всё что угодно может случиться на этих загадочных просторах, и нередко такое «что угодно» может закончиться очень плохо.

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

Находятся люди, которые спокойно спят ночью, согреваемые своей наивной уверенностью, что компьютеры совершенно предсказуемы и без устали выдают потоком правильные ответы. Как же мало им ведомо! Несмотря на серьёзнейшие усилия разработчиков чипов, создателей языков и миллионов программистов, есть ещё в программировании опасные чащи, которые могут погубить даже самых продвинутых из программистов и разработчиков.

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


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js