В параметризованной сложности люди используют сокращение с фиксированным параметром (FPT), чтобы доказать W [t] -твердость. Теоретически FPT-редукция не является редукцией за полиномиальное время, поскольку она может экспоненциально выполняться по параметру k. Но на практике все сокращения FPT, которые я видел, являются сокращением p-времени, что означает, что доказательства W [t] -твердости почти всегда подразумевают доказательства NP-полноты.
Интересно, может ли кто-нибудь дать мне сокращение FPT, которое действительно экспоненциально выполняется по параметру . Спасибо.
Следующая статья содержит сокращения для различных параметризаций Ближайшей подстроки, где время выполнения экспоненциально или в два раза экспоненциально зависит от параметра (и эта зависимость кажется неизбежной).
Д. Маркс. Ближайшие проблемы с подстрокой на малых расстояниях . SIAM Journal of Computing, 38 (4): 1382-1410, 2008.
источник
В дополнение к другим ответам следующее предложение показывает, что соответствующие понятия приводимости несопоставимы:
[2]: J. Flum, M. Grohe. Теория параметризованной сложности. Springer (2006)
источник
Возможно, это не предполагаемый ответ, но как насчет (дерандомизированного варианта) цветового кодирования для проблемы k-пути? http://en.wikipedia.org/wiki/Color-coding
Там каждый преобразует экземпляр проблемы k-path в экземпляры красочной задачи k-path путем fpt-редукции с суперполиномиальной зависимостью от k. (Создается несколько экземпляров, но их можно рассматривать как один большой экземпляр.) Поскольку красочная проблема k-path может быть решена за fpt время с помощью динамического программирования, мы можем заключить, что проблема k-path относится к FPT.
источник
Другим примером такого снижения является доказательство твердости для VC-измерения. См. «Параметризованная сложность обучения» Дауни, Эванса и Стипендиатов.
источник