Пусть $%A ( G, k )$% — полиномиальный алгоритм, который для произвольных графа $%G$% и натурального числа $%k$% с вероятностью 1 возвращает 1, если G содержит клику размера k , и с вероятностью не менее 1/2 возвращает 0, если G не содержит такой клики.

Пусть $%B ( G, k )$% — полиномиальный алгоритм, который для произвольных графа G и натурального числа k с вероятностью 1 возвращает 1, если G содержит независимое множество размера k , и с вероятностью не менее 1/2 возвращает 0, если G не содержит такого независимого множества.

Опишите полиномиальный алгоритм $%C ( G, k, m )$% , который для про- извольных графа G и натуральных чисел k и m с вероятностью 1 возвращает 1, если G содержит клику размера k или независимое множество размера m , и с вероятностью не менее 1/2 возвращает 0 иначе

задан 10 Окт '19 21:23

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

Ваш ответ

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

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

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

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

отмечен:

×273
×194

задан
10 Окт '19 21:23

показан
212 раз

обновлен
10 Окт '19 21:23

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

по почте:

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

по RSS:

Ответы

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

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