Пусть задано множество S и конечный набор его подмножеств S_1, S_2,....S_k. Для каждого множества S_i заданы два числа: l_i и h_i. Требуется выяснить, существует ли подмножество, $$T \subseteq S $$ такое, что для каждого i выполняется: $$l_i \leqslant |T \cap S_i| \leqslant h_i$$
Докажите, что эта задача входит в класс NP, описав сертификат и алгоритм верификации. Докажите, что задача является NP-трудной, сведя к ней задачу 3SAT

задан 20 Сен '16 0:11

изменен 24 Сен '16 19:17

trongsund's gravatar image


3.2k113

хотя бы с чего начать

(20 Сен '16 22:17) alois

Здесь надо сначала условие исправить. В неравенствах, судя по смыслу, вместо S должно быть S_i.

Скорее всего, здесь к какому-то частному случаю этой задачи сводится одна из известных NP-полных проблем.

(20 Сен '16 23:30) falcao

@falcao, задачу нужно как-то свести к 3-SAT

(20 Сен '16 23:50) alois

@falcao, а почему, если свести NP полную задачу к ЧАСТНОМУ случаю этой, то этого будет достаточно для доказательства?

(21 Сен '16 11:21) laminat

@laminat: если мы умеем решать данную задачу "быстро", то умеем решать и в частном случае. А из решения для частного случая (вид которого надо угадать и описать) получается решение какой-то NP-полной задачи типа SAT. Это общая логика всех таких теорем о сведЕнии.

(21 Сен '16 12:17) falcao

@falcao, есть такая идея, кажется хорошей, но строго обосновать не могу: рассмотрим 3-кнф с литералами p_1,....p_n. Составим S из литералов и их отрицаний. Для 1 <= i <= n подмножество S_i сделаем таким {p_i; not p_i} с l_i = h_i = 1; Дальше для каждой скобки С = (lit_1 or lit_2 or lit_3) --> S_C = {lit_1; lit_2; lit_3} и l_C = 1; h_C = 3

(21 Сен '16 12:36) laminat

@laminat: да, это как-то примерно так и должно делаться, но тут надо помнить конкретику из предыдущего, чтобы ссылаться.

(25 Сен '16 0:10) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×192

задан
20 Сен '16 0:11

показан
517 раз

обновлен
25 Сен '16 0:10

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

по почте:

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

по RSS:

Ответы

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

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