2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 10, 11, 12, 13, 14, 15, 16 ... 26  След.
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение22.03.2017, 21:40 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Ну, это неинтересно. Я говорил именно о языке, утверждение о принадлежности которого к $\mathbf{P}$ независимо от нашей формальной системы. Насколько мне известно, конструкции такого языка никто пока не предлагал.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение22.03.2017, 21:56 
Аватара пользователя


18/05/14
215
Москва
Xaositect в сообщении #1202722 писал(а):
Ну, это неинтересно. Я говорил именно о языке, утверждение о принадлежности которого к $\mathbf{P}$ независимо от нашей формальной системы. Насколько мне известно, конструкции такого языка никто пока не предлагал.


Не понял в каком смысле "независимо от нашей формальной системы".

Но если речь о неразрешимости вопроса о принадлежности к $P$ (отсутствие положительного теста), то это вроде легко (придумал? :)

Тоже берем проблему остановки и для каждого проверяемого "слова" кроме "обычной" проверки смотрим ещё не остановился ли некий алгоритм за число шагов, равное длине "слова". И если вдруг остановится - начинаем безобразничать! ) Тянем время экспоненциально и т.д. А поскольку проблема остановки неразрешима, то и общего способа сказать - принадлежит ли такой язык $P$ или в какой-то момент начнутся "безобразия" - невозможно.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение22.03.2017, 22:18 
Заслуженный участник
Аватара пользователя


06/10/08
6422
dmitgu в сообщении #1202728 писал(а):
А поскольку проблема остановки неразрешима, то и общего способа сказать - принадлежит ли такой язык $P$ или в какой-то момент начнутся "безобразия" - невозможно.
Ну вот тут нужны детали. Почему именно не существует какой-то другой машины для того же языка, которая безобразий не делает.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение22.03.2017, 22:26 
Аватара пользователя


18/05/14
215
Москва
Xaositect в сообщении #1202734 писал(а):
Ну вот тут нужны детали. Почему именно не существует какой-то другой машины для того же языка, которая безобразий не делает.


Так это могут быть разные языки. Есть же языки не из $P$. Вот если событие остановки случилось - язык с этих размеров "слов" становится совсем другим. А способа определить - произойдёт ли такая "метаморфоза" нет - в общем случае.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение22.03.2017, 22:29 
Заслуженный участник
Аватара пользователя


06/10/08
6422
А хотя да, Вы правы, вроде работает. Возьмем языки $L_1 \in \mathbf{P}$ и $L_2 \notin \mathbf{P}$ и сделаем язык $L_M$, состоящий из слов $w \in L_1$, для которых машина $M$ не останавливается за $|w|$ шагов, и слов $w \in L_2$, для которых $M$ останавливается за $|w|$ шагов. Тогда $L_M = L_1 \Leftrightarrow M \text{ не останавливается}$, и $L_M$ отличается от $L_2$ на конечном числе входов, если $M$ останавливается.
Странно, что эта конструкция нигде не упоминается.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение22.03.2017, 22:51 
Аватара пользователя


18/05/14
215
Москва
Xaositect в сообщении #1202740 писал(а):
А хотя да, Вы правы, вроде работает. Возьмем языки $L_1 \in \mathbf{P}$ и $L_2 \notin \mathbf{P}$ и сделаем язык $L_M$, состоящий из слов $w \in L_1$, для которых машина $M$ не останавливается за $|w|$ шагов, и слов $w \in L_2$, для которых $M$ останавливается за $|w|$ шагов. Тогда $L_M = L_1 \Leftrightarrow M \text{ не останавливается}$, и $L_M$ отличается от $L_2$ на конечном числе входов, если $M$ останавливается.
Странно, что эта конструкция нигде не упоминается.


Спасибо - красиво и понятно в Вашем оформлении ) Я как начинаю в $\LaTeX$ писать - сто раз путаюсь как что обозначается ))

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение23.03.2017, 01:20 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
dmitgu в сообщении #1202697 писал(а):
Не только:
Это было про определение $NP$, а не про язык, который вы строите.
Прежде чем говорить о принадлежности вашего языка к $NP$ и его сводимости к чему-то, нужно разобраться, как он собственно определяется.
dmitgu в сообщении #1202697 писал(а):
У нас даже способа нет отличить пустой язык от непустого
Ну да, мы в $PA$ не можем доказать, пустой этот язык или нет. Ну и что?
Если в какой-то расширенной теории можно доказать, что он пустой, то в ней же будет легко доказать, что он принадлежит $P$.
Один и тот же язык можно задавать многими разными способами, но какие способы задают один и тот же язык - зависит от модели.

Как это связано с $NP$-полнотой $3-SAT$, которая доказывается явным предъявлением сведения?
Xaositect в сообщении #1202740 писал(а):
Странно, что эта конструкция нигде не упоминается.
Может быть потому что все кому она была нужна ее придумывали по месту?
(я, прочитав ваше предложение про неразрешимость принадлежности $P$ подумал взять язык из пар $(x, y)$, таких что существует доказательство противоречивости $PA$ длины не больше $\log |x|$, а $y \in L \in EXPTIME-complete$ - это, кажется, сводится к вашему примеру если взять $M$, ищущую противоречия в $PA$)

(Оффтоп)

В списке P versus NP есть три доказательства того, что равенство $P$ и $NP$ не зависит от $PA$.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение23.03.2017, 14:19 
Аватара пользователя


18/05/14
215
Москва
mihaild в сообщении #1202778 писал(а):
Ну да, мы в $PA$ не можем доказать, пустой этот язык или нет. Ну и что?


А то, что вопрос о неравенстве $NP \ne P$ - это вопрос о неразрешимости. А формализм "языка" вообще не чувствует неразрешимость. И как Вы хотите с негодным инструментом решать интересующий вопрос?

Теперь я понимаю в некоторых деталях, почему в теории алгоритмов дело зашло в тупик. И почему
Xaositect в сообщении #1202740 писал(а):
Странно, что эта конструкция нигде не упоминается.

Потому, что тогда видна неадекватность формализма языка для решения вопросов неразрешимости, а отказываться от такого упрощения очень не хочется. Но придётся :P

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение23.03.2017, 15:40 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
dmitgu в сообщении #1202846 писал(а):
А то, что вопрос о неравенстве $NP \ne P$ - это вопрос о неразрешимости.
Что это вообще значит?
$P$ и $NP$, по определению, множества языков. Попытки ее решить в любом "другом формализме" (что такое "формализм языка"?) должны содержать (и желательно начинаться с) связь со стандартными определениями.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение23.03.2017, 16:40 
Аватара пользователя


18/05/14
215
Москва
mihaild в сообщении #1202871 писал(а):
$P$ и $NP$, по определению, множества языков. Попытки ее решить в любом "другом формализме" (что такое "формализм языка"?) должны содержать (и желательно начинаться с) связь со стандартными определениями.


Интересно узнать:
1. Если для бесконечного количества некоторых слов $(S, s)$ время поиска $p_M(|S|, |s|)$ сертификатов алгоритмом $M(S, s)$ неполиномиально дольше времени $p_{\exists}(|S|)$ проверки $R(S, s, y)$ тех же некоторых слов $(S, s)$, то $M(S, s)$ это - решение?

2. А если в целом у $R(S, s, y)$ время работы ограничено $p_{\forall}(|S|, |s|)$ ?

И как в терминах "языка" Вы выразите, что случай 1 тоже - не решение, даже если имеет место случай 2?

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение23.03.2017, 17:06 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
dmitgu в сообщении #1202883 писал(а):
это - решение?
Решение чего?
Проблемы $P$ vs $NP$? Нет конечно. То, что существует медленный алгоритм поиска сертификатов - неинтересно. Интересно, существует ли быстрый.

Но вообще фраза "алгоритм $M$ - решение $P$ vs $NP$" мне кажется настолько странной, что я скорее всего не понял ваш вопрос. Можете написать подробнее?

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение23.03.2017, 17:19 
Аватара пользователя


18/05/14
215
Москва
mihaild в сообщении #1202888 писал(а):
Проблемы $P$ vs $NP$? Нет конечно.


А почему "нет"? Алгоритм $M(S, s)$ вполне себе полиномиален для общего $p_{\forall}(|S|, |s|)$. Где в Ваших терминах есть место для $p_{\exists}(|S|)$ ? На что Вы опираетесь в своём "нет"? На то, чего нет в терминах Вашего формализма?

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение23.03.2017, 17:27 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
dmitgu, давайте уточним. У вас есть алгоритм проверки $R$, время работы которого ограничено полиномом $p_\forall$, время работы его на каком-то подмножестве $\mathbb{S}$ ограничено полиномом $p_\exists$. У вас есть алгоритм генерации сертификатов $M$, который на $\mathbb{S}$ работает сверхполиномиально по сравнению с $p_\exists$ (что эквивалентно просто "сверхполиномиально от длины входа"). Так?

(Оффтоп)

Только мне очень режет глаз использование кванторов в индексах?

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение23.03.2017, 17:59 
Аватара пользователя


18/05/14
215
Москва
Нет. Неполиномиально быстро от длины входа работает алгоритм проверки для некоторых $S$ Игнорирует $y$ (это вообще типично для всех алгоритмов проверки и больших сертификатов) и $s$.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение23.03.2017, 18:19 
Заслуженный участник
Аватара пользователя


06/10/08
6422
dmitgu в сообщении #1202846 писал(а):
А то, что вопрос о неравенстве $NP \ne P$ - это вопрос о неразрешимости. А формализм "языка" вообще не чувствует неразрешимость. И как Вы хотите с негодным инструментом решать интересующий вопрос?
Никакой это не вопрос о неразрешимости. Если зрить в корень, это вопрос о существовании для некоторой вполне конкретной задачи (распознавание языка $\mathrm{SAT}$) алгоритма решения, который обладает хорошим свойством, а именно всегда завершается за время $n^k$, где $n$ - длина входа.
Вот если для какого-то $k$ такой алгоритм существует - то $\mathbf{P} = \mathbf{NP}$. А если нет таких алгоритмов ни для какого $k$ - то не равно.
И вот это несуществование и хочется доказать. И для такого доказательства надо как-то рассматривать все алгоритмы решения одной задачи и для всех них доказать, что они плохие. И как это сделать - никто не знает, это основная проблема теории сложности.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 384 ]  На страницу Пред.  1 ... 10, 11, 12, 13, 14, 15, 16 ... 26  След.

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group