Если мы можем доказать, что задача о ранце с ограниченной емкостью решается за полиномиальное время, то весь рюкзак принадлежит P

Question

Я нашел этот вопрос в моем курсе «Алгоритм оптимизации», полный вопрос таков: если мы сможем доказать, что все задачи о ранцах с емкостью, ограниченной 100, могут быть решены за полиномиальное время, то все проблемы о ранцах принадлежат P. Является ли это предложение истинным?или ложь?Обоснуйте.

С моей книгой и некоторыми исследованиями я получил что-то вроде этого: во-первых, КП - это NP-полная проблема.При динамическом программировании оно может достигать псевдополиномиального времени, но этого недостаточно.Если, абсурдно, мы можем доказать, что КП с емкостью, ограниченной 100, можно решить за полиномиальное время, то мы можем предположить, что КП принадлежит П.

Что вы думаете о моем ответе?Я думаю, что абсурд не так прав в последнем предложении.

Answer 1

Доказательство того, что все проблемы с ранцами с ограниченной емкостью могут быть решены за полиномиальное время, не доказывает, что все проблемы с ранцами находятся в P. Если проблема в P, это означает, что она может быть решена за полиномиальное время.Это означает, что это может быть решено в O (n ^ k), где k - некоторое целое число.Большой O - это верхняя граница, означающая, что если алгоритм равен O (n), а n приближается к бесконечности, время, необходимое для выполнения алгоритмов, никогда не будет больше, чем n.Доказывая, что все проблемы с n <100 могут быть решены за полиномиальное время, это не дает гарантии для гораздо большего n.Поэтому мы не можем сказать, что существует алгоритм, который работает в O (n ^ k) и поэтому находится в P. </p>