Трудно решаемые задачи и игра «Сапёр».

Abstract

В работе на основании теории сложности задач показано, что если алгоритм раскрытия некоторого поля игры «Сапёр» существует, то он имеет сложность NP. Результаты экспериментального исследования игры показали, что алгоритм раскрытия существует с некоторой вероятностью. Этот факт позволяет предложить новую классификацию сложности задач. В приложении приводится описание методов оценки результатов в международных спортивных соревнованиях по игре в «Сапёр».