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

[mihaild]

Только не «признана» все-таки. Лучше «доказано, что игра является NP-полной задачей».
В «признании» есть нечто субъективное.

[Gaen]

В оригинале наверняка написано что-то типа «игра доказана быть NP-полной». В этом смысле у английского языка больше гибкости, что мне в нем весьма нравится.

[mihaild]

«Mario is hard, and that's mathematically official»
Я бы перевел как «Математически обоснованно, что mario — сложная игра».
Ну или всё-таки, если писать в заголовке про NP, то «Доказано, что прохождение mario — NP-трудная задача»

[ankh1989]

А я бы перевёл проще: «Марио труден и это математически официально.» :)

[asm0dey]

Математики официально думают, что пройти Марио трудно.

[Finom]

Британские математики доказали…

[mihaild]

Кроме того, утверждение «некоторые игры принадлежат к классу 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-полны

Краткая справка для забывших определения сложностных классов — неформальное напоминание:

1. Задача входит в NP, если ее решение можно проверить «быстро» (за полиномиальное время). Т.е. можно дать «короткое» (полиномиальное от размера) описание прохождения уровня, и при этом можно проверить, что это действительно прохождение
2. Задача NP-трудна, если к ней можно свести любую другую задачу из NP. Т.е. нам дан уровень для игры из NP, мы по нему можем быстро построить уровень из NP-трудной игры, такой, что эти уровни проходимы или непроходимы одновременно.
3. Задача NP-полна, если она NP-трудна и лежит в NP.
   Задача принадлежит PSPACE, если ее можно решить на «небольшой» (полиномиальной) памяти.
   PSPACE-трудность и полнота определяются аналогично NP
   


Класс PSPACE, очевидно, содержит NP — мы можем на небольшой памяти перебрать все возможные строки, и каждую из них проверить, является ли она прохождением.

[tangro]

Как, уже есть 3 коммента и еще не начался холивар P==NP vs P!=NP? Непорядок, мы же на техническом ресурсе, в конце концов!

[mihaild]

P == NP <=> P == 0 или N == 1
Давно всем известно. Проблема не стоит выеденного яйца.
«Теория NP-полноты была разработана для решения проблемы зарабатывания денег» (Н. К. Верещагин)

[mr_Flagman]

Можете немного подробней об этом решении проблемы рассказать или ссылку дать? Просмотрел все работы Верещагина, ничего подходящего не смог найти.

[mihaild]

Первая часть — это старая шутка (автор, естественно, неизвестен), которую я слышал много от кого, и никакого особого отношений Верещагин к ней не имеет.
А цитата — из лекции на спецкурсе. Не знаю, записана ли она где-то.

[mihaild]

И, кстати, если продолжать придираться — то к матану этот результат не имеет никакого отношения.

[noonesshadow]

Следующий шаг — использовать результаты прохождения игры для решения NP проблем… )

[dtestyk]

и зарабатывания криптовалюты, чтобы ее стоимость была обусловлена не расходом электричества, а интеллектуальностью действий человека.

[Frenzy]

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

[mihaild]

Да, причем тот, кто это докажет, получит миллион долларов)
А откуда цитата?

[halyavin]

Зачем доказывать определение? (Нужно только заменить NP-полные на NP, иначе подразумеваемое утверждение в обратную сторону не верно.)

[mihaild]

Думаю, имелось в видо именно что из этого утверждения следует, что P=NP.

[ertaquo]

Так ведь Donkey Kong и Mario — это одно и то же по сути, только названия различаются.

[kamelopardus]

сенсационное высказывание.

[ValdikSS]

Так ведь Хабрахабр и Автокадабра — это одно и то же по сути, только машины различаются.

[Polco]

Так ведь огурец название и то же маринада различаются по сути.

[ertaquo]

Трем человекам, прокомментировавшим выше, цитатка из вики:

Игра имеет три прямых продолжения — 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].

Если вам и этого мало, найдите скриншоты и сравните.

[silvansky]

Я знал, что в этой игрушке скрыто нечто большее! =)

И не важно, правильно или нет определены математические понятия. Главное, Марио — особенный!

[egormerkushev]

Что почитать, чтоб поумнеть в этой области игростроя? Подскажите?

[mihaild]

Что-нибудь по сложности вычислений. Можете начать, например, с «Классические и квантовые вычисления» (Вялый, Китаев, Шень), дальше по ссылкам.

[Gips]

Ни черта не понял, но Марио люблю. Так во что в итоге интересней играть NP-полные или PSPACE-полные?

[kyrie]

Сомневаюсь, что это как-то связно с интересом человека к игре… Но по статистике (из пяти игр :) NP-полные интереснее.

[dmitriid]

Да ладно :) Zelda рулит :)

[mariofag]

>Анализ вычислительной сложности пяти классических игр для Nintendo показал, что среди них есть NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга.
Ммм, что? Разве NP-полные — это не те, решения которых можно проверить за полиномиальное время? А те, которые можно решить за полиномиальное время — это класс P.

[mihaild]

NP — это те, решения которых можно проверить за полиномиальное время — или, что эквивалентно, те, которые можно решить на недетерменированной машине Тьюринга за полиномиальное время. Исторически второе определение более старое (NP = non-deterministic polynomial), но с первым в большинстве случаев удобнее работать.
NP-полные — это те, к которым сводятся все остальные задачи из NP, и при этом сами лежат в NP.

[Nastradamus]

Вот и я думаю, в Зельде, Марио всегда идеальный геймплей.

[paradoxs]

Только Марио! Только хардкор!

[kpetob]

Дух старой школы живёт только в 8мибитных приставках. Пацаны, давите гумб, варпайте в 1-2 и 4-2 левелах.