Язык $%L$% состоит из всех полиномов Жегалкина, не обращающихся в нуль. Полином Жегалкина задается списком мономов, например: $%P(x)=x_2(x_1\oplus x_3)\oplus x_2$% задается набором $%(x_1,x_2), (x_2,x_3), x_2$% так как $%P(x)=x_1x_2\oplus x_2x_3\oplus x_2$%. Показать, что $%L$% принадлежит классу полиномиальных языков.
Классу полиномиальных языков принадлежат языки, для которых существует машина Тьюринга, которая за полиномиальное по длине входа время останавливается и дает ответ "да", если на входе было слово из языка или дает ответ "нет" для слов, не принадлежащих языку.

задан 17 Апр '16 1:43

изменен 1 Май '16 17:57

@Uchenitsa: что такое класс полиномиальных языков? Такие вещи желательно сопровождать определениями или ссылками.

См. правописание фамилии математика.

(17 Апр '16 1:49) falcao

@falcao, прошу прощения за фамилию) условие исправлено

(17 Апр '16 2:19) Uchenitsa

@Uchenitsa: боюсь, что условие мне не вполне понятно. Дело в том, что любая булева функция единственным образом задаётся полиномом Жегалкина. Не обращается в 0 только тождественная единица. Любой другой полином где-то обязательно обращается в 0, что можно доказать в том числе "конструктивно". Если машина должна распознать, состоит ли список мономов из одного пустого произведения (которое в такой записи представляется парой скобок), то это тривиально. Если же полином дан в не приведённой форме, то это знаменитая проблема P=NP :)

(17 Апр '16 4:17) falcao

@falcao, в приведенной форме - имеете ввиду когда общие множители вынесены за скобки? Тогда,нет, полином представляется в неприведенной форме.

(1 Май '16 18:07) Uchenitsa
1

@Uchenitsa: в таких случаях очень желательно давать однозначную формулировку условия. Дело в том, что модификации здесь почти всегда имеют смысл, и априори не ясно, какая из них рассматривается.

Критерий того, что полином не обращается в ноль, был дан выше: это тождественная единица. Если дан список мономов, суммой которых является данный полином, и мономы могут совпадать, то нужно, чтобы кроме 1 все мономы встречались чётное число раз. Это можно проверить, например, сортировкой, время работы которой полиномиально зависит от длины входа.

(1 Май '16 18:46) falcao

@falcao, спасибо!

(1 Май '16 19:01) Uchenitsa
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Вопрос отвечен и ответ принят". Закрывший - Uchenitsa 1 Май '16 19:01

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

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

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

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

отмечен:

×277
×194
×57

задан
17 Апр '16 1:43

показан
532 раза

обновлен
1 Май '16 19:01

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

по почте:

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

по RSS:

Ответы

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

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