Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 2 |
[ Сообщений: 11 ] | На страницу 1, 2 След. |
|
Автор | Сообщение | |
---|---|---|
mathbilan |
|
|
дано понятное доказательство того факта, что 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" с уважением Билан И. |
||
Вернуться к началу | ||
Count |
|
|
Просмотрел вскользь. То, что у функции длинная ДНФ, еще не значит, что функцию нельзя быстро вычислить. Например, самая длинная ДНФ из всех функций - у линейной функции, тем не менее линейная функция вычисляется очень просто.
|
||
Вернуться к началу | ||
За это сообщение пользователю Count "Спасибо" сказали: mathbilan |
||
mathbilan |
|
|
Глубоко уважаемый Count!
Дело в том, что ДНФ эта очень специфического вида. В статье, на сколько позволял объем статьи рассмотрено все 3 возможных случая: 1) когда части конъюнктов, в производной ДНФ, проверяющие на клику имеют общую часть; 2) когда есть не пересекающиеся части конъюнктов, в производной ДНФ, проверяющие на клику; 3) когда мы что то делаем с одной единственной частью конъюнктов, в производной ДНФ, проверяющей на клику; в 1-м случае -- более чем полиномиальная трудоемкость, во 2-м случае, и в третьем случае -- тупиковая ветвь, требующая более чем полиномиального применения операции "ИЛИ" к ДНФ, из которых собирается ДНФ ответа. с глубоким уважением Билан И. |
||
Вернуться к началу | ||
Count |
|
|
Вы доказываете, что у функции, решающей задачу Клика, очень длинная ДНФ. Ну допустим. Скорее всего так и есть. На этом основании вы делаете вывод, что задача вообще не решается за полиномиальное время. А это уже неверно. Какая разница, какого там специфического вида ДНФ? ДНФ это не единственный способ вычислить функцию. Вашим способом можно доказать, что например, и линейная функция, и функция голосования трудно вычислимы, потому как любая их ДНФ, даже самая специфическая, имеет экспоненциальную длину. Тем не менее эти функции легко вычисляются за линейное время.
|
||
Вернуться к началу | ||
За это сообщение пользователю Count "Спасибо" сказали: mathbilan |
||
mathbilan |
|
|
дело в том, глубоко уважаемый Count, что длинную ДНФ можно построить только если использовать "И", а в случае с существованием клики ДНФ настолько специфична, что использование "И" затруднено, и мы чтобы получить ДНФ ответа, вынуждены использовать "ИЛИ" более чем полиномиальное число раз. И мы вычисляем ДНФ следующим образом: у нас есть переменные-начальные-данные, и их отрицания, после этого идет процесс вычислений, когда каждой промежуточной переменной, и ответу мы приписываем некоторую ДНФ, которая всегда равна значению этой переменной, при любых значениях переменных-начальных-данных (так как у L-машины нет условного перехода, и процесс вычислений детерминирован), в этом случае мы контролируем значения каждой промежуточной переменной, и переменной ответа, через приписанную ей ДНФ. А так как операции "И" и "ИЛИ" (от "НЕ" мы избавились) четко прописаны, то мы можем строить предположения, относительно того, возможна в данном случае операция "И" или нет.
(в случае операции "И" из двух ДНФ получается (грубо говоря) ДНФ число конъюнктов которой = произведение числа конъюнктов этих двух ДНФ, а в случае "ИЛИ" только сумма). с глубоким уважением Билан И. |
||
Вернуться к началу | ||
Count |
|
|
Вы вообще прочитали то, что я написал? Ну у функции длинная ДНФ, и что? Какое это имеет отношение к P=NP?
|
||
Вернуться к началу | ||
За это сообщение пользователю Count "Спасибо" сказали: mathbilan |
||
mathbilan |
|
|
я внимательно прочитал
длинную ДНФ мы можем за полиномиальное время получить только с помощью "И" ну и иногда "ИЛИ". а в данном случае для проблемы Клика, ДНФ настолько специфична, что применение "И" затруднено. поэтому NP не равно P. |
||
Вернуться к началу | ||
mathbilan |
|
|
и к тому же, ДНФ мы вычисляем НЕ в лоб, по конъюнктам.
а ставим в соответствие каждой переменной свою ДНФ. |
||
Вернуться к началу | ||
mathbilan |
|
|
глубоко уважаемый Count!
если я снова не так Вас понял, напишите! по Вашим замечаниям видно, что Вы -- профессиональный математик! и Вашим мнением я очень дорожу! с глубоким уважением Билан И. |
||
Вернуться к началу | ||
Count |
|
|
все, что я имел сказать, я уже сказал
|
||
Вернуться к началу | ||
За это сообщение пользователю Count "Спасибо" сказали: mathbilan |
||
На страницу 1, 2 След. | [ Сообщений: 11 ] |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |