Функция T получает на вход : {0, 1}^(C из n по 2) → {0, 1}, рассмотрим вход как неориентированный граф на n вершинах и положим, что T (G) = 1 тогда и только тогда, когда в G нет треугольников (это тройка вершин, попарно соединенных друг с другом). Как построить схему полиномиального размера (в стандартном базисе), вычисляющую функцию T?

задан 22 Янв '16 20:21

1

Переменные можно представить в виде $%x_{ij}$% при $%1\le i < j\le n$%. Для каждой тройки i < j < k рассматриваем конъюнкцию $%x_{ij}x_{jk}x_{ik}$%, и далее берём дизъюнкцию всех таких выражений. Понятно, что сложность имеет порядок $%O(n^3)$%. Добавляя отрицание на выходе, получаем то, что нужно.

Тут как-то совсем прямо всё получается -- может быть, имелось в виду что-то менее тривиальное.

(22 Янв '16 20:28) falcao

Оказывается, это уже было здесь.

(22 Янв '16 21:58) falcao
10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Повтор вопроса". Закрывший - falcao 22 Янв '16 21:58

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

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

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

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

отмечен:

×548
×26

задан
22 Янв '16 20:21

показан
461 раз

обновлен
22 Янв '16 21:58

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

по почте:

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

по RSS:

Ответы

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

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