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

Автор темы Владимир 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий и рекламы в форуме26.03.2008 03:07
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеАспирантура в Clemson University (Computer Science, Mathematics)03.08.2015 22:20
09.05.2001 00:44
Владимир
P=NP Позиционная алгебра логики
Я знаю как написать алгоритм, рещающий NP-полную задачу за полиномиальное время, например задачу выполнимости.
Это делается средствами позиционной алгебры логики, которую развивает Мирон Иванович Тельпиз.
Подробности на моём сайте www.plogic.h1.ru
09.05.2001 01:51
AK
Вроде нет на сайте никаких содержательны
Вроде нет на сайте никаких содержательных материалов. И сколько времени занимает это суперприведение?
09.05.2001 12:20
Дмитрий А.
Почему я должен Вам верить?
Как убедиться в правильности Ваших ВЫВОДОВ?
Кто-нибудь из известных специалистов по теории сложности (за исключением автора) проверял это доказательство???
А ведь за решение проблемы P=NP полагается 1000000$
Автор решения этой проблемы уже получил эти деньги???
09.05.2001 14:18
Владимир
Проверяли и проверяют, в частности очень
Проверяли и проверяют, в частности очень много народу из
МГУ. В конце мая или в начале июня мы проиодим большой
семинар в ИКИ на Калужской, в центре отображения.Если есть
желание можете, записаться. У нас жесткая пропускная
система. Кроме того этот семинар будет транслироваться в
интернете, а потом попадет в архив на сайте ИКИ в виде
видео.ZIP
Денег не получили, пока. Если внимательно прочитаете условие
конкурса, то увидите, что требуется признание международной
математической братвы и на обсуждение отводится год. Вот мы
и начали.
Желаю успехов в изучении ПАЛ.
09.05.2001 14:24
Владимир
На сайте достаточно содержательных матер
На сайте достаточно содержательных материалов, он постоянно обновляется, но на всё не хватает времени. Мы будем раполагать на сайте те материалы, которые уже готовы к этому. Остальное в библиотеке МГУ. Кстати Мирон Иванович Тельпиз окончил МГУ и одно время там преподавал.
09.05.2001 14:57
Дмитрий А.
А как насчёт задачи дискретного логарифмирования?
Она тоже решается за полиномиальное время???
09.05.2001 17:31
webmaster
>На сайте достаточно содержательных мате
>На сайте достаточно содержательных материалов
Вам может и достаточно, а нам не достаточно :-)
Ну там действительно ничего нет. История вопроса меня интересует меньше, чем конкретные результаты, которых пока я на Вашей страничке не обнаружил

1. Я бы посоветовал не увлекаться Java Applets и Macromedia Flash, а выкладывать побольше материалов. Неужели без апплетов нельзя обойтись? Чем больше у Вас на сайте будет наворотов, тем меньше народу сможет это прочитать.

2. А обыкновенные булевы вектор-функции это не тоже самое?

3. Самое главное - причем здесь раздел Преподаватели нашего форума. Пишите в раздел Разное. Там этой теме самое место.
09.05.2001 18:11
Владимир
Некоторые страницысайта делали мои студе
Некоторые страницысайта делали мои студенты, а они без Java Applets и Macromedia Flash жить не могут. Если уберу, кровно их обижу.
Что понимать под конкретным результатом требует уточнения. Однако то, что там есть, хватило на два месяца интенсивного изучения Бабаяновской команде в Spark центре. Я был уних два раза в неделю и видел, что люди не понимают, а люди там далеко не глупые.
Конкретные результаты есть в материалах на странице Основы Пал, могу сказать, что задачу выполнимости КНФ (3-Вып) на 600 переменных и 10000 уравнений мой компьютер (AMD7x500) решает за ночь. По классике эта задача оценивается функцией 2 в степени 600.
Сайт расчитан на людей серьёзно занимающихся этим вопросом а не для пустого трёпа. Я не собираюсь расказывать как написать программу для разминирования Minesweeper. Тот кто поймёт основы теории напишет это сам. Если найдутся такие умные, кто пришлёт мне КНФ на 32 переменных, записанную в операторном виде, тому лично отправлю первую часть книги (297 страниц).

Как попал в раздел Преподователи не понял, видимо там обсуждали вопросы связанные с NP-полными задачами. Если это возможно, пернесите все это дело в разное.
09.05.2001 18:14
Владимир
Да
09.05.2001 19:09
webmaster
> Конкретные результаты есть в материала
> Конкретные результаты есть в материалах на странице Основы Пал,
> могу сказать, что задачу выполнимости КНФ (3-Вып) на 600
> переменных и 10000 уравнений мой компьютер (AMD7x500) решает за
> ночь. По классике эта задача оценивается функцией 2 в степени
> 600.

На странице "Основы Пал" только список литературы. Видимо Вы имеете в виду ссылку на
"Тарасов В.А. Позиционная алгебра логики. Основные положения, S и FS операторы."? Но там, кажется, только 10 страниц.

Я, конечно, не утверждаю, что хорошо разбираюсь в этом вопросе, но мне кажется, что важно не то, сколько времени решается конкретная задача, а какой функцией оценивается сложность. Ну, скажем, сортировку можно выполнить за O(n log n). Полиномиальную оценку видно. А сколько конкретно будет работать программа зависит от того, что скрывается за этим "O большое". Вот я и хотел увидеть оценки такого вида. То что у Вас получается что-либо посчитать в конкретном случае не убеждает читателя в том, что при последующем увеличении n время будет расти полиномиально.
09.05.2001 23:20
Николай
У вас ошибка.
Уважаемый Владимир.
Я скачал статью http://www.iki.rssi.ru/pal/PAL1.PDF, там есть ошибка:
после фразы: "Учитывая, что все вычисления проводяться в каждом вертикальном разрядном срезе. Результирующими операторами будут:..."
идет три сторчки формул, в третьей написано что: " (110)=S(верхний индекс 2, нижний 3)", хотя на самом деле - (110)=S2,6.

09.05.2001 23:21
Владимир
Проблема в том, что для начала надо проч
Проблема в том, что для начала надо прочитать хотя бы эти десять страниц (сегодня добавил ещё 2). Для задачи 3-Вып оценка равна Cm*n*n (m-число строк, n-число уравнений, C-константа). Однако для меня важно, чтобы вы поняли, почему это так, а для этого материалов на сайте достаточно. Предлагаю вам сравнить две задачи: умножение чисел в римской (символьной) системе счисления и в позиционной. Точно такое же соотношение между задачами решаемыми методами символьной логики и позиционной.
Хочу заметить, что мы не ставили перед собой проблему доказать, P=NP. Это получилось как частный случай. Основная наша цель была разработать матаппарат позволяющий выполнять функции над функциями, а уже потом применять результирующую функцию к аргументам. Обо всем этом написано на сайте, но к моему удивлению никто не удосужился это заметить. Повторю еще раз P=NP, это частный случай, а сам по себе подход дает невероятные результаты. Просто представьте себе определение логарифма в римской системе счисления. Можно ли это сделать. Примерно в таком отношении мы находимся с символьной логикой.
09.05.2001 23:28
Владимир
Благодарю за сообщение, ошибки возможны.
Благодарю за сообщение, ошибки возможны. Я сейчас переписываю старый вариант и прямо с компьютера отправляю на сайт. Предупрежу сразу, сегодня добавил пару страниц, там есть таблицы, так они вообще не из этой оперы. Умудрился грохнуть новый вариант, вместо старого. Теперь придётся дня 4 снова всё набирать.
09.05.2001 23:41
Николай
Вы написали: "Для задачи 3-Вып оценка р
Вы написали: "Для задачи 3-Вып оценка равна Cm*n*n (m-число строк, n-число уравнений, C-константа). ". Вы, наверное, хотели написать, что n - число переменных ?
10.05.2001 00:06
Николай
Извините. Это я ошибся.
Просто в записи оператора вы пишите двоичные числа справа налево.
10.05.2001 01:01
webmaster
Дочитал эти 10 страниц до конца. Даже ст
Дочитал эти 10 страниц до конца. Даже стало интерсно, чем там дело кончится. Впечатление следующее: много разных определений (пока не понятно зачем), и ни одного доказательства. Только определения и примеры. Пока не очень видно, как там можно получить заявленное P=NP...
Ждем-с продолжения :-)

Замеченные очепятки:

стр. 1. абзац 1. "алгебрЫ"
стр. 4. 4 строка снизу "a \subset E(0,1)"
видимо надо "a \in E" или "a \in {0,1}".
или там какое-то хитрое обозначение?
10.05.2001 01:26
Николай
Вопрос по статье.
В начале пункта "Позиционные FS операторы" написано, что совершенный набор имеет длину 2^(n-1). А по моему, его длина 2^n-1.

И еще в этом же пункте мне не понятно как согласуется длинна FS оператора, записаного с помощью фигурных скобок с длинной набора. Что делать, когда длинна оператора больше длинны набора? Например, как понимать формулу: Xi or Xi+k = {(0^(i-1)1^(i-1))^k1^(i+k-1)}. При i=1, k=1 это означает X1 or X2 = {010111}. И как теперь применить 6-и символьный FS оператор к 3-х символьному набору?
10.05.2001 02:58
Николай
Я тоже дочитал до конца.
Я не понял как по дезьюнкту строится его запись в позиционной системе. Например как по X1 or X2 (для 5 переменных) получить STMM?

И самое главное. Как потом считать дизьюнкцию в позиционной системе? Как, например, получить, что STMM&SMTM=SSSTM ?
10.05.2001 13:17
Владимир
Да ошибся
10.05.2001 16:28
Владимир
Сообщение всем, о согласованности длин с
Сообщение всем, о согласованности длин совершенного набора и FS оператора.
В статье даны следующие определения
Для набора Xn=(x1, x2, …, xn) совершенным называется такой двоичный набор Xns=(x1,x2,x2,x3,x3,x3,x3,…,xn,xn,…, xn), в котором при i=1,2, …,n аргумент xi содержится 2^(i-1) раз, т.е. набор Xns имеет длину N=2^(2n)-1. Следовательно, простой оператор, согласованный с совершенным набором Xns , должен содержать N+1 символов. Такие операторы и называются FS операторами.
При записи FS операторов мы будем пользоваться следующим правилом: если a =(0,1), то a^k=a…aaa….a, где в правой части a входит не k раз, а 2^k раза.

Нужно обратить внимание, что не k, а 2 в степени k. Поэтому длина оператора не может быть нечетной и она всегда кратна степени два. Зачем это нужно. Запишем таблицу истинности для трех переменных
Таблица
X1 X2 X3
0 0 0
1 0 0
0 1 0
1 1 0
0 0 1
1 0 1
0 1 1
1 1 1
Как видно длина таблицы для 3 переменных равна 8. Кроме того, первая переменная повторяется 4 раза, вторая 2, третья 1. Совершенный набор и FS оператор используются для описания таблиц истинности. Я думаю, что зачем нужны повторения и сколько их будет, и что они будут всегда согласованы ясно из таблицы
В дальнейшем мы никогда не будем работать с таблицами в явном виде, а будем выполнять действия над операторами. Но для того, чтобы понимать, что на самом деле происходит, и были введены эти определения. Позиционная логика, вообще не работает с аргументами, только с операторами. Результатом всех действий будет оператор, и вот тогда его можно применить к аргументам и сразу получить готовое решение. Вместо аргументов используются селекторные функции. Это два ключевых понятия ПАЛ. Селекторные функции необходимы для того, чтобы задать структуру булевой формулы. В результате мы будем иметь только операторы и это позволяет нам построить операторное исчисление. При этом всегда нужно помнить, что любые действия над операторами, фактически являются действиями над таблицей истинности. При этом длина таблицы истинности равна 2 в степени N, длина оператора равна N. Это было отправной точкой при доказательстве P=NP.

Благодарю всех за оказанное внимание а особенно за сообщения об ошибках.
Сайт постоянно обновляется, однако очень медленно, не хватает времени. Сейчас группа состоит из 4-х человек: Я, М.И. Тельпиз, Петров Игорь и Фомин Андрей. Двое из нас живут в Москве: я и Петров. Остальные в Тарусе. Я отвечаю за сайт, семинары, статьи и связь с Тарусой. Кроме того, моя статья на сайте «Основы ПАЛ ……..», это подготовка курса лекций, который я согласился прочитать в МГУ в следующем уч. году.
Пока всё.




Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти