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

Автор темы Владимир 
ОбъявленияПоследний пост
ОбъявлениеРекомендации по использованию теха в нашем форуме15.04.2017 21:40
ОбъявлениеАспирантура в Clemson University (Computer Science, Mathematics)03.08.2015 22:20
ОбъявлениеАспирантура в Норвегии и Германии07.12.2015 14:00
10.05.2001 22:33
Владимир
>Я не понял как по дезьюнкту строится ег
>Я не понял как по дезьюнкту строится его запись в позиционной системе. Например как по X1 >or X2 (для 5 переменных) получить STMM?

Для пяти переменных можно получить только STMMM, то есть символов в операторе всегда столько сколько переменных. Частично на этот вопрос ответ в рубрике согласованность длин на этом форуме. Однако то, что я сказал достаточно легко понять если построить таблицу истинности для 5 переменных и внимательно посмотреть на на строчку X1 or X2. Если будет непонятно, то спросите снова, попытаюсь объяснить подробней. Однако у меня в статье есть таблица для 4-х, можно её использовать.

>И самое главное. Как потом считать дизъюнкцию в позиционной системе? Как, например, получить, что STMM&SMTM=SSSTM ?

Отмечу сразу, еще раз, символов в операторе всегда столько сколько переменных. Поэтому
STMM&SMTM=SSSTM быть не может, а STMM&SMTM=SSTM может. Иначе говоря, в ПАЛ выполнение операций не может расширить область определения задачи.
Как выполнить операцию над операцией это тртий ключевой момент ПАЛ, и последний. Сейчас я вам этого рассказать не могу, вы меня не поймете. Перед этим надо много ещё чего рассказать. Однако, забегая в вперёд скажу, в ПАЛ не всегда можно выполнить операцию над операторами. Иногда остаются хвосты от операторов тогда, можно заменить конъюнкцию на дизъюнкцию, инвертировав операторы. Но и после этог могут остаться хвосты, а может ничего не остаться.
Мы работаем с КНФ и ДНФ, как известно любую ФАЛ можно записать таким образом, а там используются свои приемы, но об этом будет всё сказано в дальшем.
11.05.2001 00:19
Владимир
Это потому, что символы операторов обраб
Это потому, что символы операторов обрабатываются в обратном порядке, а так как в ПАЛ не работают с аргументами, то в результате мы получим привычный способ обработки позиционных операторов.
11.05.2001 00:21
Владимир
Просто дурное наследие
Просто дурное наследие
11.05.2001 12:54
Николай
Понятно. Ждем продолжения.
Я понял, как вы по таблице для 4-ех переменных получаете позиционные записи. Например
X1 v X2 = 0111011101110111=SESESESE=
=SESEM=SEMM=STMM
Но у меня не получилось сделать тоже самое например для формулы
(X1 v X2) & (X1 v X3) = 0101011101010111=
SSSESSSE = SSSEM
И что делать дальше?

А на счет операций над операторами в позиционной системе, с нетерпением жду продолжения вашей статьи. :-)
11.05.2001 19:27
Студент 2-го курса
Где Вы будете читать эти лекции?
На каком факультете и при какой кафедре?
11.05.2001 21:53
Владимир
Пока не знаю. Можете спросить у Русакова
Пока не знаю. Можете спросить у Русакова Александра, тел. 238-56-16, он заведует школой юнных математиков при МГУ. Для меня, чем младше контингент, тем лучше. Не обременен богёжем предвзятых мнений и понятий.
12.05.2001 00:01
Дмитрий А.
На вашем сайте написано:"Такие задачи,
На вашем сайте написано:"Такие задачи, как умение разлагать большие числа на множители, брать дискретный логарифм в конечном поле и многие другие, которые входят в перечень NP-полных задач".
Не могли ли вы указать источники в которых доказано, что задача дискр. логарифмирования - NP-полная задача ?
12.05.2001 01:49
Владимир
Сообщение всем. Как читать устаревшие пр
Сообщение всем. Как читать устаревшие препринты.
Если вы возьмете препринты в библиотеке, то прочитав их, вы обнаружите, что они отличаются от моей статьи на сайте. Почему это так.
1.На данный момент мы переопределили некоторые базовые понятия. Это не касается самих идей. Однако касается базового алфавита, раньше он был А(1), а теперь А(0). Я, человек который занимался разработкой компьютеров (бортовых), а там, как известно есть только (0,1). Но этого на все хватает. Кроме того, я так думаю, что всё, что здесь излагается, это только для специалистов узкого круга, которым интересна вся внутренняя “кухня” того, как живет и чем дышит компьютер. Не секрет, что мы занимаемся тем, как сделать их умнее. Эта наука сейчас называется Theoretical Computer Science (TCS), как это звучит на русском, точного определения пока не знаю. Есть несколько вариаций, но не одна пока не закрепилась.
Так вот, проблема алфавита более важна для человека, чем для компьютера. Человеку, более важно, чтобы он мог описать мир более кратко и понятно для себе подобных. Однако здесь наступает предел. Нет алфавитов с бесконечным числом символов. Даже китайским иероглифам есть предел. Мы же, европейцы, используем 20-40 букв (символов), и с помощью этого описываем мир, тот же самый, что китайцы с помощью нескольких тысяч иероглифов. Кстати мир от этого не меняется, то есть он не зависит от способа его описания. Живёт сам по себе.
Поэтому мы решили: компьютеру компьютерево, человеку человечьево. В результате за базовый взяли алфавит А(0).
2. Кроме алфавита изменены правила продукций. Известно, из алгебры логики, что над данной областью определения определены два типа функций, прямые и обратные. Мы работаем только с прямыми, а для работы с обратными ввели понятие инвертирования. Как оно получается, те кто прочёл статью поймут сразу. (Кто не понял пишите) Оно там кругом в выкладках.
3. Основная идея осталась та же. Но, что теперь делать с нами, с людьми? Вопрос пока открытый. Есть варианты.
1. Мыслить в представлениях ПАЛ.
2. Переводить наши мысли из символьной логики в ПАЛ и обратно.
3. Гибридный вариант.
Все три приемлемы. Я за несколько лет я привык к ПАЛ, и это даже лучше, видишь и понимаешь больше. Почитайте Кастаньеду, Гурджиева, Успенского, Левингстона и прочих, об этом там написано очень много, но не математическим языком. Я думаю, что переход от римской системы счисления к позиционной то же произошел не за один день.
Однако пока мы интенсивно работаем над системой перевода из символьной логики в ПАЛ и обратно. Моё личное мнение, что проще затратить силы и средства на это, чем переучивать весь мир.
Поэтому, получив старый препринт в руки, смотрите на основные идей. Если сами в состоянии перевести выкладки из алфавита А(1) в А(0), хвала вам и поздравления. Если нет, то пишите и спрашивайте. Вообще по поводу того, что если что не понятно, то спрашивайте сразу не стесняйтесь. Отвечу при первой же возможности. Кстати, вы можете напрямую обращаться к Мирону Ивановичу, на моём сайте есть все ссылке на него. Однако, сейчас он загружен больше, чем я, но его ответ, я думаю, через несколько лет попадёт в раритеты. Главное не стесняйтесь, спрашивайте. Постараемся на всё ответить. Однако не забывайте, то что я написал в начале статьи, он в своих обозначениях использует греческие буквы и другие символы. Его алфавит богаче, чем мой. Поэтому формулируйте вопрос словами.
Искренне Ваш.

P.S. Я всю следующую неделю буду в Тарусе.
12.05.2001 01:57
Владимир
Мы занимаемся Theoretical Computer Scien
Мы занимаемся Theoretical Computer Science и Позиционной Алгеброй Логики.
На большее у меня нет сил. Спросите у Мирона Ивановича Тельпиза.

12.05.2001 15:49
Дмитрий А.
Как Вы проверяли,то что эта (NP-полная)
Как Вы проверяли,то что эта (NP-полная) задача решается за полиномиальное время? Вы запускали свою программу на компьютере и смотрели на время работы,или у Вас есть теоретическое доказательство?
А если нет теоретического обоснования,то возможно же,что Вы проверяли программу для огранниченного числа наборов,для которых эта задача действительно является полиномиальной?
12.05.2001 17:29
Владимир
Есть теоретическое доказательство. Как э
Есть теоретическое доказательство. Как это сделано, обсуждается здесь на форуме. На данный момент мы уже далеко ушли от таких пустых вопросов. Сейчас главный вопрос: как это получается и почему. Если есть желание, присоединяйтесь. Напомню еще раз. Мы не ставили перед собой проблему доказать, что P=NP. Это один из частных выводов теории ПАЛ. Хотя, для нас очень приятный. Просто мы этого не ожидали, но то что можно получить с помощью ПАЛ гораздо больше чем доказать, что P=NP.
12.05.2001 22:05
Студент 2-го курса
P=NP-пустой вопрос???
И наверное очень простой.
Почему же на него ещё никто не ответил?
13.05.2001 11:43
Владимир
Потому что не использовали ПАЛ. Вопрос в
Потому что не использовали ПАЛ. Вопрос возведения в степень то же простой, но попробуйте это сделать в римской системе счисления. Например XXVI в степени XI. Сразу всё станет ясно.
14.05.2001 19:57
Человек и атомный крейсер
Да-с. Меня радуют заявления докладчика,
Да-с. Меня радуют заявления докладчика, что он ходил дважды в неделю к Бабаяну, а его никто не понял. Я помню одного старичка, который ходил на мехмат и всем рассказывал, как дифференцировать целые числа. А его никто не слушал. И ведь тоже наверное старикан радовался:"Ишь ты, сам академик меня слушал, да и тот не понял."

Вот мне говорят, что P=NP. Я говорю:"На стол колоду, господа..." Мне (в замен !) предлагают 12 страничный документ без конца и никак не связанный с темой обсуждения. Ладно, посмотрим. Корявый язык простителен. То, что идея всей работы для математика заключена в 3 строчках, это простительно. То, что изложение бесцельно, это уже хуже. Что нам предлагается? Алфавит из 4(6) букв. Слова длины n соответствуют булевым функциям над 2^{n+1} аргументами. Ну соответствуют, и ладненько. Заметим, что слов таких
2^{2n}, а функций "чуть" больше, 2^{2^{n+1}}. Такое соответствие не может быть эпи. Ну не эпи, хрен с ним. Вполне возможно, что для такого узкого подмножества есть быстрый алгоритм проверки выполнимости (таковой есть и для дизъюнктивных нормальных форм и = нетривиальности). Заметьте, что в любом алфавите и эпиморфном способе нотации существует функция с дважды экспоненциальной длиной записи.

Короче, мой вердикт - не обращайте на это внимание, не тратьте время.
15.05.2001 12:09
A.M.
Человек и атомный крейсер писал(а): >
Человек и атомный крейсер писал(а):
>
> Короче, мой вердикт - не обращайте на это внимание, не тратьте
> время.

Присоединяюсь к данному пожеланию.
15.05.2001 14:46
Владимир
Внимательней читайте, то что в этих 12-т
Внимательней читайте, то что в этих 12-ти страницах есть. Если не составит труда, сходите в библиотеу и возъмите соостветствыющие материалы. Пока, могу пригласить на семинар. Подробности на сайте.
15.05.2001 14:47
Владимир
Каждому своё.
Каждому своё.
15.05.2001 14:53
Владимир
Мы делаем семинар. Он будет 7 июня в 11
Мы делаем семинар. Он будет 7 июня в 11 00 в здании ИКИ. Подробности на сайте.
04.06.2001 22:40
Владимир
Не будет семинара 7 июня, по крайней мер
Не будет семинара 7 июня, по крайней мере для студентов. Общий семинар будет в сентябре. Летом мы проведем несколько небольших семинаров в Тарусе. Желающие you are welcome. Для этого свяжитесь со мной, по электронной почте.
19.09.2001 03:41
Алексей Ремизов
чем всё закончилось?
Сообщите, пожалуйста, если кто-то знает, чем всё это дело закончилось?
Были ли эти семинары и какой результат?

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

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