Измерение сложности NP-комплектного

Question

Например, известно, что проблема решения с заданным покрытием является NP-полной проблемой. Входными данными этой проблемы является юниверс U, семейство S подмножеств U и целое число k ().

Одна вещь, с которой меня смущает то, что если мы допустим k=1, то, очевидно, проблему можно решить за время |S|, просто проверив каждый элемент в S. В более общем случае, когда k является константой, проблема может быть решенным за полиномиальное время |S|. Таким образом, временная сложность становится экспоненциально высокой только тогда, когда k также увеличивается с |S|, как |S|/2, |S|/3...

Итак, вот мои вопросы:

1. Мое текущее понимание состоит в том, что измерение сложности времени NP-полной задачи измеряется с точки зрения худшего случая. Кто-нибудь может сказать мне, если понимание правильно?

2. Я видел, как кто-то доказал, что другая проблема является NP-трудной, показав, что проблема решения, охватывающая множество, с входными данными <U,S,|U|/3> можно свести к этой проблеме. Мне просто интересно, почему он оказался только для <U,S,|U|/3>, вместо <U,S,ARBITRARY k>?? Является ли такое доказательство надежным?

Большое спасибо!

Answer 1

Сложность времени измеряется как функция размера входного экземпляра. Размер входного экземпляра может быть измерен в битах. Размер входного экземпляра увеличивается как любой из входных U, S, а также k увеличение. Таким образом, вопрос, на который пытаются ответить, состоит в том, сколько времени требуется, например, для решения проблемы размера экземпляра. 2n биты против проблемы размера экземпляра n,

Так что просто нужно увеличить размер всего входного экземпляра, и в этом конкретном случае это означает увеличение размера U и / или S и / или k,

Чтобы ответить на два ваших вопроса:

1. Да, используется наихудшая временная сложность: вы ищете самую сложную проблему размера ввода n и вы правильно заметили, что проблема (того же размера), вероятно, становится более сложной, когда вы увеличиваете больше параметров, чем один.

2. Было бы лучше увидеть доказательство, на которое вы ссылаетесь, но мышление выглядит так:

   Я даю полиномиальное уменьшение размера решения проблемы покрытия множества n к размеру моей проблемы m, Если размер входного экземпляра задачи решения покрытия множества увеличивается до 2n тогда результатом сокращения будет размер моей проблемы 2m потому что есть прямое соответствие между входным размером U, S, а также k и размер ввода моей проблемы.

   Таким образом, все решающие проблему экземпляры размера решения n сопоставить с моей проблемой экземпляров размера m, Таким образом, если я буду искать самый сложный случай решения проблемы покрытия множеств, используя это сокращение, я найду самый сложный пример моей проблемы размера m,

РЕДАКТИРОВАТЬ

Из доказательства в вашей связанной статье:

Доказательство. Мы сокращаем произвольный экземпляр задачи с 3-мя покрытиями, в котором нам дается юниверс U, семейство S подмножеств U, так что каждое подмножество содержит 3 элемента, и нас спрашивают, можем ли мы (точно) покрыть все U, используя |U|/3 элемента S - к игре с однородными ресурсами и графиками размера 3.

Как вы правильно сказали, им нужно преобразовать все случаи проблемы set-cover в свою проблему. Но они используют сокращение от другой проблемы: проблема Exact 3-cover, которая доказана как NP-полная в "Компьютерах и труднопреодолимости - MR Garey, DS Johnson, 1979".

Точная проблема с 3-мя покрытиями подобна задаче решения с заданным покрытием, но с |U| = 3t а также S представляет собой набор из трехэлементных подмножеств U,