Рубрика «класс NP»

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

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

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

Опубликован быстрый алгоритм для задачи изоморфизма графов - 1
Эти два графа являются изоморфными

Математик Ласло Бабай (László Babai) с факультета компьютерных наук и математики Чикагского университета представил быстрый новый алгоритм для решения задачи изоморфизма графов — одной из фундаментальных проблем теории сложности вычислений. Алгоритм приводит проблему очень близко к классу P. По мнению некоторых специалистов, это один из самых значительных результатов в теоретической информатике за десятилетие, если не за несколько десятилетий.
Читать полностью »

Игра Super Mario признана NP полной задачей

Математический анализ сложности пяти классических игр для Nintendo показал, что среди них есть NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга. Проще говоря, это математически очень сложные задачи, сравнимые с задачей коммивояжёра или проблемой раскраски графа.

Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Кроме того, отдельные игры других серий принадлежат к классу NP, а некоторые игры из серии Zelda — к классу PSPACE.
Читать полностью »

Игра Super Mario определена как NP полная задача

Математический анализ сложности пяти классических игр для Nintendo показал, что среди них есть NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга. Проще говоря, это математически очень сложные задачи, сравнимые с задачей коммивояжёра или проблемой раскраски графа.

Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Отдельные игры других серий принадлежат к классу NP, а некоторые игры — к классу PSPACE.
Читать полностью »

Доказано, что игра Super Mario является NP полной задачей

Анализ вычислительной сложности пяти классических игр для Nintendo показал, что среди них есть NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга. Проще говоря, это математически очень сложные задачи, сравнимые с задачей коммивояжёра или проблемой раскраски графа.

Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Отдельные игры других серий принадлежат к классу NP, а некоторые игры — к классу PSPACE.
Читать полностью »


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