пример приведения полиномиального решения к NP-полному

Если я сведу NP-полную проблему к неизвестной проблеме P, тогда я уверен, что P сам по себе является NP-полной.

Нет, это плохо сформулировано. Если NP-полная проблема A сводится к проблеме P, все, что мы можем сказать, это то, что любая проблема в NP сводится к P. Чтобы сказать, что P является NP-полным, нам нужно дополнительно знать, что P сам находится в NP.

То, что вы, вероятно, собирались сказать, было

Если я уменьшу NP-полную проблему до некоторой неизвестной проблемы P в NP, я уверен, что P сам по себе NP-полный

Теперь к вашему первоначальному вопросу.

приведем пример, показывающий, что мы можем свести полиномиальную разрешимую задачу P к NP-полной.

Рассмотрим проблему, известную как 2-SAT: Если дана логическая формула в конъюнктивной нормальной форме, такая, что каждая дизъюнкция содержит не более двух переменных, скажите, является ли она выполнимой.

Решение этой проблемы по алгоритму, предложенному Aspvall, Plass & Tarjan (1979) включает построение графа импликации и поиск всех его сильно связных компонентов. В статье доказывается, что формула выполнима тогда и только тогда, когда граф импликации не содержит сильно связной компоненты, включающей некоторую переменную вместе с ее отрицанием. Это также показывает, что этот алгоритм линейен по размеру кодировки формулы.

So

1. существует линейный алгоритм для 2-SAT.
2. 2-SAT сводится к задаче неограниченной логической выполнимости, известной как SAT.

Это дает пример полиномиально решаемой задачи (2-SAT), которая сводится к NP-полной задаче (SAT).