Сложность некоторых задач в NP?

Я хочу обобщить некоторые проблемы на сложности. Какие из них можно решить в поливремени?

I) поиск максимального подполного графа данного графа = проблема клики

II) выбрать некоторые элементы среди n объектов, в которых заданы значения и веса, так, чтобы сумма весов выбранных элементов не превышала определенную границу, а сумма значений была максимальной

III) нахождение всех циклов графа

IV) Поиск пути, который посещает каждую вершину ровно один раз = Определить, что граф является гамильтоновым.

Я думаю, что IV — это гамильтонов путь, который является NP-полным, III — NP-сложным и NP-полным, II — NP-полным, а I — NP-полным. так что 0 из них решены за политайм.

Кто может по-хорошему прояснить мне NP-Hard и NP-Complete этих проблем? Я прав?


graph algorithm np complexity-theory np-complete
person Community    schedule 07.04.2015    source источник
comment
II) — это задача о рюкзаке, которая является поливременной, если веса не являются частью входного размера, т. е. решение полиномиально только с точки зрения n.   -  person pkacprzak    schedule 07.04.2015
comment
Что вы подразумеваете под максимальным подграфом данного графа?   -  person templatetypedef    schedule 07.04.2015
comment
@templatetypedef это проблема клики   -  person    schedule 07.04.2015
comment
@pkacprzak Это новость для меня - есть ссылка?   -  person G. Bach    schedule 07.04.2015
comment
@templatetypedef я редактирую свой вопрос   -  person    schedule 07.04.2015
comment
@ G.Bach Я думаю, что это ссылка на алгоритм псевдополиномиального времени для рюкзака, который является экземпляром управляемого алгоритма с фиксированными параметрами.   -  person templatetypedef    schedule 08.04.2015

Ответы (2)


arrow_upward
1
arrow_downward

Как вы заметили, части (1), (2) и (4) — это известные NP-трудные задачи (максимальная клика, рюкзак и гамильтонов путь). Однако этих проблем нет в NP, потому что NP состоит из проблем принятия решений (вопросов, на которые можно ответить либо «да», либо «нет»), а это не проблемы принятия решений.

Часть (3) более тонкая. Эта проблема является проблемой подсчета — цель состоит в том, чтобы определить, сколько существует объектов определенного типа — а не проблемой принятия решения, поэтому она не может быть в NP. Насколько мне известно, на самом деле неизвестно, насколько сложна эта проблема. Известно, что если ее можно решить за полиномиальное время, то P = NP (см. по этой ссылке для подробностей), и конкретное доказательство показывает, что это также NP-сложно.

Если P NP, то ни одна из них не может быть решена за полиномиальное время. Если любую из них можно решить за полиномиальное время, то P = NP. Все они NP-трудны.

Надеюсь это поможет!

person templatetypedef    schedule 07.04.2015
comment
Сложный вопрос, не могли бы вы уточнить, какой из них является NP-Complete, какой NP и какой NP-HARD? - person ; 07.04.2015
comment
@user4249446 user4249446 Ни одна из них не является NP-полной, поскольку ни одна из них не находится в NP (NP состоит из проблем принятия решений, которые задают вопросы «да/нет», и все эти проблемы требуют некоторого объекта вместо вопроса «да/нет»). Следовательно, ни одна из них не может быть NP-полной, поскольку для того, чтобы задача была NP-полной, она должна принадлежать NP. Однако все они NP-трудны. - person templatetypedef; 08.04.2015
comment
версия решения Knapsack 0/1 является NP-HARD? G имеет цикл Гамильтона = G имеет путь Гамильтона = NP-Complete? я прав ? - person ; 08.04.2015
comment
@ user4249446 Все версии решения Q1, Q2 и Q4 находятся в NP и NP-hard, так что да, они NP-полные. Я не уверен, находится ли версия решения (3) в NP, поскольку я не вижу, как вы могли бы проверить ответ за полиномиальное время. - person templatetypedef; 08.04.2015
comment
Версия решения Knapsack - это NP-Hard, а не NP конкурировать? Я ошибаюсь ? - person ; 08.04.2015
comment
@user4249446 user4249446 Это неправильно. Версия задачи решения о рюкзаке находится в NP и NP-сложной, поэтому по определению она NP-полная. - person templatetypedef; 08.04.2015
comment
Хотя верная и полезная информация о том, что (1), (2) и (4) не в NP, я хотел бы добавить, что в контексте NP-сложности люди обычно говорят о версии решения задач оптимизации. - person G. Bach; 08.04.2015

arrow_upward
0
arrow_downward

Поскольку меня спросили о ссылке, я отправляю свой комментарий в качестве ответа:

II) выбрать некоторые элементы из n объектов, в которых заданы значения и веса, так, чтобы сумма весов выбранных элементов не превышала определенную границу, а сумма значений была максимальной

Это задача о рюкзаке, которая является поливременной, если веса не являются частью входного размера, т.е. решение полиномиально только по n.

Он работает в O(n * W), где W — максимально допустимый вес. Конечно, это может быть не полиномиально, если W связано с n, например, если W = 2^n.

Вы можете прочитать об этом здесь:

http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming_in_advance_algorithm

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/knapsackdyn.htm

person pkacprzak    schedule 07.04.2015