В своей статье (стр. 503) Гарей и Джонсон замечают:
... может существовать NP-полная задача, которая не является NP-полной в строгом смысле и не разрешима алгоритмом псевдополиномиального времени ...
Кто-нибудь знает некоторые возможные проблемы со свойствами, упомянутыми выше?
Я думаю, что возможным ответом на этот вопрос может быть список NP-полных задач в обычном смысле, так что для них не известен псевдополиномиальный алгоритм.
ds.algorithms
np-hardness
np
Александр бондаренко
источник
источник
Ответы:
Я не знаю, заинтересованы ли вы в том, чтобы услышать более подробно мой комментарий к вашему вопросу, но в любом случае здесь более подробно.
Если P = NP, каждая проблема в NP может быть решена за полиномиальное время и, следовательно, за псевдополиномиальное время, что означает, что ни одна проблема не удовлетворяет вашему требованию, как отметил Магнус в своем ответе. Итак, предположим, что P ≠ NP в оставшейся части этого ответа.
Поскольку P ≠ NP, существует язык L ∈NP ∖ P, который не является NP-полным (теорема Ладнера). Рассмотрим следующую проблему:
Прямое произведение
Экземпляра и L- экземпляра : m натуральных чисел a 1 ,…, a m и k целых чисел b 1 ,…, b k ∈ {0,1}.
Вопрос : оба из следующих удержания?
(1) m целые числа a 1 ,…, a m образуют случай да проблемы разделения.
(2) к -битовой строке б 1 ... б к принадлежит L .
Следуя статье Гэри и Джонсона, определите функцию Length как m + ⌈log max i a i ⌉ + k, а функцию Max - как max i a i .
Обычной процедурой является проверка (i) того, что он NP-полон в слабом смысле, (ii), что он не имеет алгоритма псевдополиномиального времени, и (iii) что он не NP-полон в сильном смысл.
(Подсказки: (i) Членство в NP следует из того факта, что и проблема Разделения, и L. находятся в NP. Для NP-твердости уменьшите Разделение до этой проблемы. (Ii) Постройте псевдополиномиальное преобразование из L в эту проблему. (iii) Построить псевдополиномиальное преобразование из этой задачи в L , используя тот факт, что Разделение имеет алгоритм псевдополиномиального времени.)
В этой конструкции нет ничего особенного в проблеме Разделения: вы можете использовать свою любимую задачу со слабым NP-полным с алгоритмом псевдополиномиального времени.
источник
Я бы сказал, что ответ явно отрицательный (то есть никто не знает), потому что никто не знает, можно ли решить NP-полные задачи за полиномиальное время, не говоря уже о псевдополиномиальном времени. (Каждый полиномиальный алгоритм, конечно, псевдополиномиальный.) Если вы можете найти в NPC проблему, которая не может быть решена в псевдополиномиальном времени, вы только что доказали, что P ≠ NP, поэтому я думаю, что можно с уверенностью сказать, что таких примеров не будет производится в ближайшее время.
источник