Измерение сложности NP-complete

Например, известно, что задача решения множества-покрытия является 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>?? Надежно ли такое доказательство?

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


np np-hard complexity-theory set-cover np-complete
person kostio    schedule 06.01.2014    source источник
comment
Как насчет того, чтобы дать ссылки на сочинения этого парня, чтобы нам не пришлось гадать? Также полезно иметь ссылку и правильное определение проблемы покрытия набора, а также объяснение ваших обозначений скобок.   -  person David Grayson    schedule 06.01.2014

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

  1. Да, используется наихудшая временная сложность: вы ищете самую сложную задачу с размером входных данных n и правильно заметили, что задача (того же размера), вероятно, усложняется по мере увеличения количества параметров, а не только одного.
  2. #P4# <блочная цитата> #P5# #P6#

ИЗМЕНИТЬ

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

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

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

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

person Jakub Kotowski    schedule 06.01.2014
comment
Большое спасибо за ваш ответ. Я думаю, мы должны свести проблему набора-покрытия к моей проблеме. Но кажется, что ваш ответ на вопрос 2 говорит об обратном. Я имею в виду документ (152.3.140.1/~dima/papers/complexityAAAI10.pdf) (доказательство находится прямо над разделом заключения), автор свел задачу о множестве-покрытии ‹U,S,|U|/3› к проверяемой задаче. Насколько я понял, мне кажется более убедительным свести ‹U,S,k› к задаче. - person kostio; 06.01.2014
comment
А, насчет направления вы конечно правы.. такая ошибка новичка.. ответ исправлю - person Jakub Kotowski; 06.01.2014
comment
обновил ответ на основе вашего комментария и после просмотра сокращения в статье - person Jakub Kotowski; 06.01.2014
comment
Теперь я понимаю. Спасибо, что рассказали мне точную проблему с тремя обложками и ссылку. Это очень полезно и решило большую проблему для меня. Большое спасибо!!!!! :) - person kostio; 07.01.2014