По следам публикации P != NP (для которой, кстати, опубликовано опровержение), хочу поделиться ссылкой на статью В.Ф. Романова, в которой он показывает, как можно свести решение NP-полной задачи «3-ВЫП» к полиномиальному алгоритму.
Напомню, что любую задачу из класса NP можно «полиномиально свести» к любой из NP-полных задач. Значит если если существует полиномиальный алгоритм для решения хотя бы одной задачи, то потенциально любую NP-полную задачу можно также решить полиномиальным алгоритмом.
Напомню, что любую задачу из класса NP можно «полиномиально свести» к любой из NP-полных задач. Значит если если существует полиномиальный алгоритм для решения хотя бы одной задачи, то потенциально любую NP-полную задачу можно также решить полиномиальным алгоритмом.