Любое натуральное число может рассматриваться как битовая последовательность, поэтому ввод натурального числа аналогичен вводу последовательности 0-1, поэтому проблемы с NP-заполнением с натуральными входами, очевидно, существуют. Но есть ли естественные проблемы, то есть те, которые не используют...
Это повторение предыдущего вопроса . Рассмотрим следующую беспристрастную идеальную информационную игру между двумя игроками, Алисой и Бобом. Игроки получают перестановку целых чисел от 1 до n. На каждом ходу, если текущая перестановка увеличивается, текущий игрок проигрывает, а другой игрок...
Мафия - популярная ролевая игра на вечеринках, подробное описание доступно на википедии http://en.wikipedia.org/wiki/Mafia_%28game%29 . В основном это работает следующим образом: В начале каждому из игроков тайно отводится роль, связанная либо с мафией, либо с городом. Каждая роль может иметь...
История вопроса Этот вопрос мотивирован настольной игрой под названием «Дракула». В этой игре есть один вампир и четыре охотника, цель охотников - поймать вампира. Действие игры происходит в Европе. Игра выглядит следующим образом: 1. Игрок-охотник сажает всех охотников в города. В одном городе...
Как можно показать, что определенное свойство не может быть выражено в 2-CNF (2-SAT)? Существуют ли игры, такие как игры в гальку? Похоже, что классическая игра с черной галькой и игра с черной и белой галькой для этого не подходят (они завершены PSPACE, согласно Hertel и Pitassi, SIAM J of...
Знается ли / изучена ли эта совершенная информационная игра на графиках? Учитывая график , два игрока поочередно выбирают ребро или изолированный узел. Если игрок выбирает ребро два узла и удаляются вместе с их падающими ребрами. Если игрок выбирает изолированный узел, узел удаляется. Первый игрок,...
У Конвея очень приятная конструкция из сюрреалистических чисел. Это «числа», которые содержат как действительные числа, так и порядковые числа, полностью упорядочены и имеют все свойства поля (за исключением того, что они образуют не множество, а класс). Смотрите, например, этот PDF или Википедию...