#Do_you_understand
Еще один крайне необычный пример задачи из NP класса - это серия Mario. Трудно сказать, кому пришла в голову идея анализировать игрушку на принадлежность к теоретической информатике, однако факт есть факт.
Выражается сложность в том, что для некоторых изданий невозможно легко проверить, удастся ли в принципе пройти игру до конца. Т.е. вполне возможно, что некоторые уровни будут слишком сложными, так что, если тебя постигла неудача - это не ты играть не умеешь, это игра NP-полная.
P.S. Статья об анонимности в Интернете получается очень объемной, поэтому выложу ее утром.
О чем рубрика
Еще один крайне необычный пример задачи из NP класса - это серия Mario. Трудно сказать, кому пришла в голову идея анализировать игрушку на принадлежность к теоретической информатике, однако факт есть факт.
Выражается сложность в том, что для некоторых изданий невозможно легко проверить, удастся ли в принципе пройти игру до конца. Т.е. вполне возможно, что некоторые уровни будут слишком сложными, так что, если тебя постигла неудача - это не ты играть не умеешь, это игра NP-полная.
P.S. Статья об анонимности в Интернете получается очень объемной, поэтому выложу ее утром.
О чем рубрика