0

Классифицируйте как можно точнее в полиномиальной иерархии язык A = {(F, G, H) | для любой раскраски F в красный и зелёный цвета найдётся либо красный подграф, изоморфный G, либо зелёный подграф, изоморфный H}. Будет ли он полон в соответствующем классе?

задан 18 Дек '17 2:53

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

Ваш ответ

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

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

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

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

регистрация »

отмечен:

×84

задан
18 Дек '17 2:53

показан
632 раза

обновлен
18 Дек '17 2:53

Связанные вопросы

0 Задачи на сложность

0 Посчитать О-большое

0 Функции T1(n) и T2(n) заданы рекуррентными формулами

0 Постройте как можно более быстрый алгоритм

0 Замкнут ли класс NP относительно дополнения?

0 NP полнота языка простых чисел

0 Теория вычислимости

0 Найти Theta-асимптотику и вычислить функцию

1 Срочно нужна помощь в теории алгоритмов (про 2-КНФ, n-КНФ и SAT)

1 PSPACE, EXPTIME, P, NP классы

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

по почте:

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

по RSS:

Ответы

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

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