Рассмотрим следующую задачу: FILLAPIX : Дана таблица размера m × n, в которой каждая клетка либо пуста, либо содержит число от 0 до 9. Выяснить, можно ли покрасить некоторые клетки таблицы в белый цвет таким образом, чтобы для всякой клетки a, содержащей число k, количество граничащих с ней клеток белого цвета, включая саму клетку a, равнялось k?

Необходимо доказать, что FILLAPIX полиномиально сводима к SAT.

задан 21 Май '17 23:09

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×243

задан
21 Май '17 23:09

показан
284 раза

обновлен
21 Май '17 23:09

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru