Что такое псевдополиномиальное время? Чем он отличается от полиномиального времени?
Что такоепсевдополиномиальное время? Чем он отличается от полиномиального времени? Некоторые алгоритмы, которые работают в псевдополиномиальном времени, имеют время выполнения, например O (nW) (для0/1 Рюкзак Задача) или O (√n) (дляпробное подразделение); почему это не считается полиномиальным временем?