Сведение решения NP-полной задачи «3-выполнимость» к алгоритму с полиномиальной сложностью

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

Напомню, что любую задачу из класса NP можно «полиномиально свести» к любой из NP-полных задач. Значит если если существует полиномиальный алгоритм для решения хотя бы одной задачи, то потенциально любую NP-полную задачу можно также решить полиномиальным алгоритмом.



Владимир Федорович Романов, профессор кафедры ИСИМ Владимирского государственного университета, уже несколько лет пытается опубликовать свою работу в журналах с высоким уровнем авторитета, но рецензенты попросту не хотят брать на себя ответственность и публиковать эту работу, постоянно мотивируя отказы нелепыми придирками к форматированию. Для меня это выглядит смешно, потому что более педантичного человека, чем профессор Романов, я не встречал.

На данный момент статья переведена на английский язык и я знаю, что Владимир Федорович ведет переписку с иностранными журналами, чтобы ее опубликовать.

Публикую здесь ссылку на его работу в надежде, что она получит хоть какой-то резонанс в научных кругах и на нее обратят внимание.

Неортодоксальные комбинаторные модели
на основе несогласованных структур
Романов В.Ф. (romvf@mail.ru)
Владимирский государственный университет

http://zhurnal.ape.relarn.ru/articles/2007/143.pdf

Обновление от 01.09.2010

Сегодня беседовал с Владимиром Федоровичем.

Оказывается английская версия статьи лежит рядом:

Non-orthodox combinatorial models based on discordant
structures
Romanov V. F. (romvf@mail.ru)
Vladimir state university

http://zhurnal.ape.relarn.ru/articles/2007/143e.pdf