Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 11 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: NP is not P
СообщениеДобавлено: 14 апр 2014, 11:35 
Не в сети
Начинающий
Зарегистрирован:
14 апр 2014, 11:31
Сообщений: 7
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте, коллеги!
дано понятное доказательство того факта, что NP не равно Р
30.10.2013 года опубликован №5/2013 журнала “Eastern European Scientific Journal”. Ссылка на журнал в интернете http://www.auris-verlag.de по ссылке Journal и далее Eastern European Scientific Journal October 2013 или http://www.auris-verlag.de/mediapool/99 ... 310_2_.pdf с.114

название статьи: "NP not equal to P"
с уважением Билан И.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: NP is not P
СообщениеДобавлено: 17 апр 2014, 14:17 
Не в сети
Начинающий
Зарегистрирован:
17 апр 2014, 14:13
Сообщений: 10
Cпасибо сказано: 0
Спасибо получено:
4 раз в 4 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Просмотрел вскользь. То, что у функции длинная ДНФ, еще не значит, что функцию нельзя быстро вычислить. Например, самая длинная ДНФ из всех функций - у линейной функции, тем не менее линейная функция вычисляется очень просто.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Count "Спасибо" сказали:
mathbilan
 Заголовок сообщения: Re: NP is not P
СообщениеДобавлено: 17 апр 2014, 19:11 
Не в сети
Начинающий
Зарегистрирован:
14 апр 2014, 11:31
Сообщений: 7
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Глубоко уважаемый Count!
Дело в том, что ДНФ эта очень специфического вида.
В статье, на сколько позволял объем статьи рассмотрено все 3 возможных случая:
1) когда части конъюнктов, в производной ДНФ, проверяющие на клику имеют общую часть;
2) когда есть не пересекающиеся части конъюнктов, в производной ДНФ, проверяющие на клику;
3) когда мы что то делаем с одной единственной частью конъюнктов, в производной ДНФ, проверяющей на клику;
в 1-м случае -- более чем полиномиальная трудоемкость,
во 2-м случае, и в третьем случае -- тупиковая ветвь, требующая более чем полиномиального применения операции "ИЛИ" к ДНФ, из которых собирается ДНФ ответа.

с глубоким уважением Билан И.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: NP is not P
СообщениеДобавлено: 18 апр 2014, 09:30 
Не в сети
Начинающий
Зарегистрирован:
17 апр 2014, 14:13
Сообщений: 10
Cпасибо сказано: 0
Спасибо получено:
4 раз в 4 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Вы доказываете, что у функции, решающей задачу Клика, очень длинная ДНФ. Ну допустим. Скорее всего так и есть. На этом основании вы делаете вывод, что задача вообще не решается за полиномиальное время. А это уже неверно. Какая разница, какого там специфического вида ДНФ? ДНФ это не единственный способ вычислить функцию. Вашим способом можно доказать, что например, и линейная функция, и функция голосования трудно вычислимы, потому как любая их ДНФ, даже самая специфическая, имеет экспоненциальную длину. Тем не менее эти функции легко вычисляются за линейное время.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Count "Спасибо" сказали:
mathbilan
 Заголовок сообщения: Re: NP is not P
СообщениеДобавлено: 18 апр 2014, 10:18 
Не в сети
Начинающий
Зарегистрирован:
14 апр 2014, 11:31
Сообщений: 7
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
дело в том, глубоко уважаемый Count, что длинную ДНФ можно построить только если использовать "И", а в случае с существованием клики ДНФ настолько специфична, что использование "И" затруднено, и мы чтобы получить ДНФ ответа, вынуждены использовать "ИЛИ" более чем полиномиальное число раз. И мы вычисляем ДНФ следующим образом: у нас есть переменные-начальные-данные, и их отрицания, после этого идет процесс вычислений, когда каждой промежуточной переменной, и ответу мы приписываем некоторую ДНФ, которая всегда равна значению этой переменной, при любых значениях переменных-начальных-данных (так как у L-машины нет условного перехода, и процесс вычислений детерминирован), в этом случае мы контролируем значения каждой промежуточной переменной, и переменной ответа, через приписанную ей ДНФ. А так как операции "И" и "ИЛИ" (от "НЕ" мы избавились) четко прописаны, то мы можем строить предположения, относительно того, возможна в данном случае операция "И" или нет.
(в случае операции "И" из двух ДНФ получается (грубо говоря) ДНФ число конъюнктов которой = произведение числа конъюнктов этих двух ДНФ, а в случае "ИЛИ" только сумма).
с глубоким уважением Билан И.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: NP is not P
СообщениеДобавлено: 18 апр 2014, 10:51 
Не в сети
Начинающий
Зарегистрирован:
17 апр 2014, 14:13
Сообщений: 10
Cпасибо сказано: 0
Спасибо получено:
4 раз в 4 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Вы вообще прочитали то, что я написал? Ну у функции длинная ДНФ, и что? Какое это имеет отношение к P=NP?

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Count "Спасибо" сказали:
mathbilan
 Заголовок сообщения: Re: NP is not P
СообщениеДобавлено: 18 апр 2014, 12:21 
Не в сети
Начинающий
Зарегистрирован:
14 апр 2014, 11:31
Сообщений: 7
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
я внимательно прочитал :)
длинную ДНФ мы можем за полиномиальное время получить только с помощью "И" ну и иногда "ИЛИ".
а в данном случае для проблемы Клика, ДНФ настолько специфична, что применение "И" затруднено.
поэтому NP не равно P.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: NP is not P
СообщениеДобавлено: 18 апр 2014, 12:25 
Не в сети
Начинающий
Зарегистрирован:
14 апр 2014, 11:31
Сообщений: 7
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
и к тому же, ДНФ мы вычисляем НЕ в лоб, по конъюнктам.
а ставим в соответствие каждой переменной свою ДНФ.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: NP is not P
СообщениеДобавлено: 19 апр 2014, 10:02 
Не в сети
Начинающий
Зарегистрирован:
14 апр 2014, 11:31
Сообщений: 7
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
глубоко уважаемый Count!
если я снова не так Вас понял, напишите!
по Вашим замечаниям видно, что Вы -- профессиональный математик!
и Вашим мнением я очень дорожу!
с глубоким уважением Билан И.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: NP is not P
СообщениеДобавлено: 21 апр 2014, 09:15 
Не в сети
Начинающий
Зарегистрирован:
17 апр 2014, 14:13
Сообщений: 10
Cпасибо сказано: 0
Спасибо получено:
4 раз в 4 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
все, что я имел сказать, я уже сказал

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Count "Спасибо" сказали:
mathbilan
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 11 ]

Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved