Тельпиз доказал, что NP=P, или не доказал?

Сообщение №2791 от Алексей 01 марта 2002 г. 03:35
Тема: Тельпиз доказал, что NP=P, или не доказал?

Мирон Тельпиз утверждает, что им доказано NP=P.
Мне же сдается, что у него есть ошибка.
Кто-нибудь владеет информацией на этот счет? В печати я не встречал ни опровержения, ни подтверждения (хотя я, видимо, мало читаю).
Заранее благодарен.


Отклики на это сообщение:

А где вы это прочитали? Я такого не слышал, но мое мнение, что для доказательтва необходим пересмотр аксиоматики. В рамках существующей это наврядли возможно.


Кое-что прочитать можно здесь:

Miron Telpiz's P=NP Page


> Кое-что прочитать можно ...
Что и сделал. На доказательство не похоже,
скорее - некоторое развитие метода резолюций...


Никакого доказательства я не углядел.
Кстати, на этот счет рекомендую статью ftp://ftp.mccme.ru/pub/ium/stnotes/smale.ps.gz - намного более содержательно.


> > Кое-что прочитать можно ...
> Что и сделал. На доказательство не похоже,
> скорее - некоторое развитие метода резолюций...

На этом сайте есть кое-какие статьи по теме, проливающие свет на то, о чем собственно идет речь.

Позиционная алгебра логики


> На этом сайте есть кое-какие статьи по теме, проливающие свет на то, о чем собственно идет речь.
Этот сайт я как раз и имел в виду, когда задавал вопрос. К сожаленью он ничего не проясняет относительно самой проблемы.
Т.к. заявленного в нем и в помине нет.


> > На этом сайте есть кое-какие статьи по теме, проливающие свет на то, о чем собственно идет речь.
> Этот сайт я как раз и имел в виду, когда задавал вопрос. К сожаленью он ничего не проясняет относительно самой проблемы.
> Т.к. заявленного в нем и в помине нет.

Про М.Тельпиза там написано: "До выхода книги он не желает появляться на свет." Так что, ждем выхода книги - а там видно будет.
Успешным прецедентом подобного подхода к решению серьезных проблем было доказательство Andrew Wiles Великой Теоремы Ферма, над которой он работал 7 лет вдали от всех. Инетесные детали есть в интервью с самим Andrew.

Solving Fermat: Andrew Wiles


> Успешным прецедентом подобного подхода к решению серьезных проблем было доказательство Andrew Wiles Великой Теоремы Ферма, над которой он работал 7 лет вдали от всех. Инетесные детали есть в интервью с самим Andrew.

Выйдет книга или нет - сейчас уже все-равно, т.к. Тельпиз не сможет доказать то, что хочет. Если кому-то интересно, могу сообщить: NP-проблема решается в духе континуум-гипотезы, а не в духе теоремы Ферма. NP-гипотеза непротиворечива и независима от аксиоматики ZF.


> Выйдет книга или нет - сейчас уже все-равно, т.к. Тельпиз не сможет доказать то, что хочет. Если кому-то интересно, могу сообщить: NP-проблема решается в духе континуум-гипотезы, а не в духе теоремы Ферма. NP-гипотеза непротиворечива и независима от аксиоматики ZF.

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


> На чем основывается сие утверждение? FLT я помню тоже подозревали в независимости от используемой аксиоматики, а потом ее вдруг доказали.
Сейчас уже можно и нужно подозревать все нерешенные проблемы.
Если же человек говорит, что он доказал, значит он уже не подозревает. Я тоже нечто утверждаю. Увы, поскольку обещан млн.,то нескромно будет здесь вдаваться в излишние подробности. Но, Тельпиз ошибается, если только он не изменил свою точку зрения - честное слово "дворянина".


>>честное слово "дворянина".


>>честное слово "дворянина".

честное слово - не доказательство. Хотелось бы услышать чтонибудь поконкретней.


Цитата из "Ответов на все вопросы":

Вопрос: Знаете ли вы, "P=NP"2уже доказано? Ходят слухи, что это так.

Кнут: Что именно вы слышали?

Вопрос: Что-то из России.

Кнут: Из России? Это новость для меня. Я не думаю, что кто-то уже доказал это. Но, я знаю, Энди Яо (Andy Yao) надеется решить эту задачу в ближайшие пять-десять лет. Он вдохновлен Эндрю Уайлсом (Andrew Wiles), посвятившим семь лет доказательству Последней Теоремы Ферма. Они оба из Принстона. Если кто и способен сделать это, то это Энди.

Три или четыре года назад появилась статья в китайском журнале, в которой один профессор заявлял что способен решить NP-сложную задачу3 за полиномиальное время. Он рассматривал задачу о кликах4, и использовал очень хитрый способ их представления. Метод предположительно работал за полиномиальное время, но реально требовал что-то порядка n12 шагов, так что было невозможно его проверить уже при n=5. Поэтому было очень сложно искать ошибки в его доказательстве. Я поехал в Стэнфорд и засел за него с нашими дипломниками, и нам потребовалась пара часов, чтобы найти ошибку. Я написал автору письмо об этом, и еще через пару месяцев он ответил, что "нет, нет, там нет ошибки". Я решил больше с этим не связываться. Я сделал свою часть работы. Но я не верю, что эта задача решена. Это самая сложная задача из стоящих сегодня перед современной теоретической информатикой, а возможно, и всей современной наукой.


> >>честное слово "дворянина".
Честное слово дворянина может быть дано только дворянином


Кнут: Но, я знаю, Энди Яо (Andy Yao) надеется решить эту задачу в ближайшие пять-десять лет. Он вдохновлен Эндрю Уайлсом (Andrew Wiles), посвятившим семь лет доказательству Последней Теоремы Ферма. Они оба из Принстона. Если кто и способен сделать это, то это Энди.

Если Яо и насчитал 5-10 лет, то значит его метод не рациональный, потом погрешность расчетов что-то очень большая. Скорее всего он плясал от Уайлса, а не от сути задачи. А про китайцев, как про чукчей, анекдоты уже можно слагать - машинного времени ему, видите ли, не хватило. Нет, господин Кнут в данном вопросе ну никак не может быть авторитетом. По моим данным еще сам Кук с компанией бьется, и давно, между прочим, но и от него перестали сведения поступать (впрочем сведений о тех, кто занимается этой задачей, мне как раз и не хватает).
Теперь чуть-чуть по-существу. Задача не так сложна как ее пытаются представить. Она будет очень сложной только в том случае, если пытаться доказать или опровергнуть саму NP-гипотезу. Что можно и нужно доказать, я уже высказывался на этот счет. Для сравнения же лучше держать перед собой не пример с Уайлсом, а пример с пятым постулатом - две тысячи лет искали решение, которое оказалось понятным дошкольникам. Там не могли прямую кривой вообразить, тут не могут вообразить кривых алгоритмов. Задача только немного посложней. Не буду говорить, что она совсем проста, но в сравнение не идет по сложности с очень многими другими задачами.
Откуда я это знаю? В ближайшее время и вы узнаете. По правилам милионы дают только за опубликованные доказательства. Но Яо пусть поторопится (пять лет - это слишком).


принципа позиционности с чисел на функции является более важным и можно предположить, что без такого продолжения вряд ли можно доказать, что NP = P.
no vedi prinzip pozizionosti nedokazan

a vobshe on sobludaetsa na nedeterminiskich kompiutore.
no togda etotprinzip ponaten.

to tak kak kagdui NP algorithm rashaetsa na
nedeterminiskom kompe za P vrema.
to na nedeterminiskom kompe NP=P


Я не специалист, может я чего не понимаю, но в работах Тельпиза мне немедленно бросилось в глаза следующее:

1. "Теорема. Класс NP-полных задач совпадает с классом P."
Т.е. человек явно не владеет терминологией. Ведь NP вовсе не есть Класс NP-полных задач. Поправьте, если ошибаюсь.

2. "Например, автор знаменитого метода резолюций Дж.Робинсон в публичной лекции, прочитанной в институте ICOT в Токио в 1983 году, указал..."
Т.е человек не знает, что Джулия Робинсон - женщина. Поправьте, если ошибаюсь, может это другой Дж. Робинсон?

3. Совершенно кошмарный английский "перевод".

После этого я конечно не стал вникать в "содержательную" часть работы, но все же просмотрел. Ничего содержательного я там не нашел также.
Опять же, ни на что не претендую, это просто мое мнение-недоумение.

> > На этом сайте есть кое-какие статьи по теме, проливающие свет на то, о чем собственно идет речь.
> Этот сайт я как раз и имел в виду, когда задавал вопрос. К сожаленью он ничего не проясняет относительно самой проблемы.
> Т.к. заявленного в нем и в помине нет.


Уважаемые коллеги
Здесь прозвучала мысль о том, что гипотеза P=NP сходна с пятым постулатом Евклида или континиум-гипотезой. Это вполне разумные мнения, но я считаю, что здесь нет ничего общего. Нельзя отдельно ввести аксиомы P=NP и P<>NP и доказывать их независимость от остальных аксиом - ведь гипотеза конструктивна. Если P=NP, тогда задачу реализации ДНФ можно решить полиномиально - т.е нужно предъявить алгоритм. Естественно-научная гипотеза что это не так подтверждается многими попытками придумать полиномиальный алгоритм, но вот доказательства невозможности такого рода очень трудны :). Хотя мне интересно ознакомиться с вариантом доказательства и я отдаю должное смелости автора, но все же отношусь к таким попыткам скептически.


Вопрос: Знаете ли вы, "P=NP" уже доказано? Ходят слухи, что это так.

Кнут: Что именно вы слышали?

Вопрос: Что-то из России.

Кнут: Из России? Это новость для меня. Я не думаю, что кто-то уже доказал это. Но, я знаю, Энди Яо (Andy Yao) надеется решить эту задачу в ближайшие пять-десять лет. Он вдохновлен Эндрю Уайлсом (Andrew Wiles), посвятившим семь лет доказательству Последней Теоремы Ферма. Они оба из Принстона. Если кто и способен сделать это, то это Энди.

Три или четыре года назад появилась статья в китайском журнале, в которой один профессор заявлял что способен решить NP-сложную задачу за полиномиальное время. Он рассматривал задачу о кликах, и использовал очень хитрый способ их представления. Метод предположительно работал за полиномиальное время, но реально требовал что-то порядка n^12 шагов, так что было невозможно его проверить уже при n=5. Поэтому было очень сложно искать ошибки в его доказательстве. Я поехал в Стэнфорд и засел за него с нашими дипломниками, и нам потребовалась пара часов, чтобы найти ошибку. Я написал автору письмо об этом, и еще через пару месяцев он ответил, что "нет, нет, там нет ошибки". Я решил больше с этим не связываться. Я сделал свою часть работы. Но я не верю, что эта задача решена. Это самая сложная задача из стоящих сегодня перед современной теоретической информатикой, а возможно, и всей современной наукой.

Д.Кнут "Ответы на все вопросы"


> Здесь прозвучала мысль о том, что гипотеза P=NP сходна с пятым постулатом Евклида или континиум-гипотезой. Это вполне разумные мнения, но я считаю, что здесь нет ничего общего. Нельзя отдельно ввести аксиомы P=NP и P<>NP и доказывать их независимость от остальных аксиом - ведь гипотеза конструктивна. Если P=NP, тогда задачу реализации ДНФ можно решить полиномиально - т.е нужно предъявить алгоритм.
Сразу уточню, что Алексей Ч. это тот самый Алексей, но не Alexis.
Общее все-таки есть, уместно вспомнить, что континуум гипотезу тоже критиковали за то, что просили предъявить пересчет вещественных чисел, раз уж их число алеф-ноль. Воз как известно и поныне там. Существование полиномиальных алгоритмов - это не то же самое, что и их конструирование. Тем более, что акиомы накладываю свою печать и на предметную область, в данном случае на множество задач.


> Здесь прозвучала мысль о том, что гипотеза P=NP сходна с пятым постулатом Евклида или континиум-гипотезой. Это вполне разумные мнения, но я считаю, что здесь нет ничего общего. Нельзя отдельно ввести аксиомы P=NP и P<>NP и доказывать их независимость от остальных аксиом - ведь гипотеза конструктивна. Если P=NP, тогда задачу реализации ДНФ можно решить полиномиально - т.е нужно предъявить алгоритм.

Конструктивность гипотезы зависит от точки зрения на конструктивность.
Известны примеры примитивно-рекурсивных функций, для которых невозможно
определение скорости роста (следует из теор. Гёделя). Для NP в самой простой
форме ЕСТЬ оптимальный примитивно-рекурсивный алгоритм - но неизвестно, как
быстро он работает.


Книга уже вышла - буквально несколько дней назад. А несколько часов назад я ее купил, встретившись для этого с Владимиром Тарасовым. Тираж маленький - всего 150 экз., но распродано пока еще не все. Кто желает стать счастливым обладателем - списывайтесь по электронной почте с В.Тарасовым и вперед. Только сегодня или завтра он уезжает в Тарусу к Тельпизу. Сегодня у меня была короткая беседа с Тарасовым. Он утверждает, что математики с мехмата МГУ и из института им. Стеклова уже признали доказательство NP=P, правда случилось это совсем недавно - всего месяц-другой назад. Так что ждемс скорой факторизации 4096-битовых чисел, и RSA - звиздец.


Да - доказал.
Еще в 1989 году.
И не только RSA ждёт такая судьба.

> Книга уже вышла - буквально несколько дней назад. А несколько часов назад я ее купил, встретившись для этого с Владимиром Тарасовым. Тираж маленький - всего 150 экз., но распродано пока еще не все. Кто желает стать счастливым обладателем - списывайтесь по электронной почте с В.Тарасовым и вперед. Только сегодня или завтра он уезжает в Тарусу к Тельпизу. Сегодня у меня была короткая беседа с Тарасовым. Он утверждает, что математики с мехмата МГУ и из института им. Стеклова уже признали доказательство NP=P, правда случилось это совсем недавно - всего месяц-другой назад. Так что ждемс скорой факторизации 4096-битовых чисел, и RSA - звиздец.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100