Comments 34
Только не «признана» все-таки. Лучше «доказано, что игра является NP-полной задачей».
В «признании» есть нечто субъективное.
В «признании» есть нечто субъективное.
В оригинале наверняка написано что-то типа «игра доказана быть NP-полной». В этом смысле у английского языка больше гибкости, что мне в нем весьма нравится.
Кроме того, утверждение «некоторые игры принадлежат к классу NP, а некоторые — к классу PSPACE» выглядит несколько странно — любая задача, принадлежащая NP, автоматически принадлежит PSPACE.
Если кому-то лень читать статью, то:
Краткая справка для забывших определения сложностных классов — неформальное напоминание:
Если кому-то лень читать статью, то:
- Super Mario Brothers и Donkey Kong Coungry — NP-полны
- Legend of Zelda — NP-трудна
- Ocarina of Time, Majora's Mask, Oracle of Seasons, The Minish Cap и Twilight Princess — PSPACE-полны
Краткая справка для забывших определения сложностных классов — неформальное напоминание:
- Задача входит в NP, если ее решение можно проверить «быстро» (за полиномиальное время). Т.е. можно дать «короткое» (полиномиальное от размера) описание прохождения уровня, и при этом можно проверить, что это действительно прохождение
- Задача NP-трудна, если к ней можно свести любую другую задачу из NP. Т.е. нам дан уровень для игры из NP, мы по нему можем быстро построить уровень из NP-трудной игры, такой, что эти уровни проходимы или непроходимы одновременно.
- Задача NP-полна, если она NP-трудна и лежит в NP.
Задача принадлежит PSPACE, если ее можно решить на «небольшой» (полиномиальной) памяти.
PSPACE-трудность и полнота определяются аналогично NP
Класс PSPACE, очевидно, содержит NP — мы можем на небольшой памяти перебрать все возможные строки, и каждую из них проверить, является ли она прохождением.
Как, уже есть 3 коммента и еще не начался холивар P==NP vs P!=NP? Непорядок, мы же на техническом ресурсе, в конце концов!
P == NP <=> P == 0 или N == 1
Давно всем известно. Проблема не стоит выеденного яйца.
«Теория NP-полноты была разработана для решения проблемы зарабатывания денег» (Н. К. Верещагин)
Давно всем известно. Проблема не стоит выеденного яйца.
«Теория NP-полноты была разработана для решения проблемы зарабатывания денег» (Н. К. Верещагин)
И, кстати, если продолжать придираться — то к матану этот результат не имеет никакого отношения.
Следующий шаг — использовать результаты прохождения игры для решения NP проблем… )
(присоединяясь к предыдущим ораторам) И вобще, вот это утверждение «NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга» ещё надо доказать :)
Так ведь Donkey Kong и Mario — это одно и то же по сути, только названия различаются.
сенсационное высказывание.
Так ведь Хабрахабр и Автокадабра — это одно и то же по сути, только машины различаются.
Так ведь огурец название и то же маринада различаются по сути.
Трем человекам, прокомментировавшим выше, цитатка из вики:
Если вам и этого мало, найдите скриншоты и сравните.
Игра имеет три прямых продолжения — Donkey Kong Jr., Donkey Kong 3 и Donkey Kong '94 для Game Boy (последнюю можно также рассматривать как римейк, но после четырёх оригинальных уровней идут более ста новых). Также игра Donkey Kong II выходила на Game & Watch. Прыгун, уже в Donkey Kong Jr. получивший имя «Марио», фигурировал в более поздних играх серии Mario и стал талисманом компании Nintendo.
Ма́рио (яп. マリオ Марио?, англ. Mario) — персонаж видеоигр компании Nintendo, созданный Сигэру Миямото. Являясь талисманом Nintendo и основным героем серии, Марио появился в более чем 200 видеоиграх с момента своего создания. Впервые появился в аркаде Donkey Kong под изначальным именем Прыгун (англ. Jumpman), и был он тогда не водопроводчиком, а плотником[1].
Если вам и этого мало, найдите скриншоты и сравните.
Я знал, что в этой игрушке скрыто нечто большее! =)
И не важно, правильно или нет определены математические понятия. Главное, Марио — особенный!
И не важно, правильно или нет определены математические понятия. Главное, Марио — особенный!
Что почитать, чтоб поумнеть в этой области игростроя? Подскажите?
Ни черта не понял, но Марио люблю. Так во что в итоге интересней играть NP-полные или PSPACE-полные?
>Анализ вычислительной сложности пяти классических игр для Nintendo показал, что среди них есть NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга.
Ммм, что? Разве NP-полные — это не те, решения которых можно проверить за полиномиальное время? А те, которые можно решить за полиномиальное время — это класс P.
Ммм, что? Разве NP-полные — это не те, решения которых можно проверить за полиномиальное время? А те, которые можно решить за полиномиальное время — это класс P.
NP — это те, решения которых можно проверить за полиномиальное время — или, что эквивалентно, те, которые можно решить на недетерменированной машине Тьюринга за полиномиальное время. Исторически второе определение более старое (NP = non-deterministic polynomial), но с первым в большинстве случаев удобнее работать.
NP-полные — это те, к которым сводятся все остальные задачи из NP, и при этом сами лежат в NP.
NP-полные — это те, к которым сводятся все остальные задачи из NP, и при этом сами лежат в NP.
Вот и я думаю, в Зельде, Марио всегда идеальный геймплей.
Только Марио! Только хардкор!
Sign up to leave a comment.
Доказано, что игра Super Mario является NP-полной задачей