Сведение Решения Np-Полной Задачи О 3-Выполнимости К Алгоритму Полиномиальной Сложности

Вслед за публикацией P != NP (для которой, кстати, опубликовано опровержение ), хочу поделиться ссылкой на статью В.

Ф.

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

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

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

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

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

Мне это кажется смешным, потому что более педантичного человека, чем профессор Романов, я не встречал.

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

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

Неортодоксальные комбинаторные модели на основе противоречивых структур Романов В.

Ф.

([email protected]) Владимирский государственный университет http://zhurnal.ape.relarn.ru/articles/2007/143.pdf Обновление от 01.09.2010 Сегодня я разговаривал с Владимиром Федоровичем.

Оказывается, англоязычная версия статьи находится рядом: Неортодоксальные комбинаторные модели, основанные на дискордантных структуры Романов В.

Ф.

([email protected]) Владимирский государственный университет http://zhurnal.ape.relarn.ru/articles/2007/143e.pdf Теги: #Алгоритмы #вычислительная сложность #доказательство #Чулан