Сложность измерения NP-комплекта

Question

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

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

Так here're мои вопросы:

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

2. Я видел, что кто-то доказал, что другая проблема NP-hard, показывая, что проблема с установкой покрытия с вводом <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.

EDIT

Из доказательства в связанном документе:

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

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

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