Здравствуйте, alebab, Вы писали:
T>>NP-полная = эквивалентна классу NP-полных задач (т.е. сводима к одной из них) T>>NP-трудная = стопудово полиномиально неразрешима
A>Ваши рассуждения немного противоречивы. Согласен с определением NP-полноты, кроме того, что записано в скобках.
A>Любую полиномиально разрешимую задачу можно свести к любой NP-полной. однако полиномиально разрешимые задачи не становятся изза этого NP-полными.
В данном контексте под сводимостью подразумевается равносильность.
A>Ровно поэтому я и не утверждаю, что задача о "суммарной строке" NP-полна. А всего лишь говорю, что она NP-трудна
