2014 dxdy logo

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

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





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


16/07/14
1272
Москва
dmitgu, тогда явно выпишите, пожалуйста, какие у какого алгоритма на каком множестве ограничение на время работы.

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


18/05/14
137
Москва
Xaositect в сообщении #1202910 писал(а):
вопрос о существовании для некоторой вполне конкретной задачи (распознавание языка $\mathrm{SAT}$


Если верна теорема Кука. А она не верна, если надо учитывать вот такое:
dmitgu в сообщении #1202894 писал(а):
$p_{\exists}(|S|)$


Xaositect в сообщении #1202910 писал(а):
И для такого доказательства надо как-то рассматривать все алгоритмы решения одной задачи и для всех них доказать, что они плохие


Согласен - примерно то же я пытаюсь сделать в своём доказательстве (если там нет ошибок), но я представлял себе немного иной взгляд - такой универсальный алгоритм-решение, который решает любую задачу (каким-то стандартным образом сформулированную) из $NP$. И при таком подходе - вопрос о неразрешимости. Но да - это менее сильный случай. Может нет универсального, но есть частный алгоритм-решение для каждой задачи из NP- как в криптографии с окрытым ключом. Однако, если верен Ваш подход, то верен и мой (он - необходимое условие для Вашего). И в этом смысле я озвучил менее сильное требование, которое тоже имеет место быть. Вроде бы :-)

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


06/10/08
5772
dmitgu в сообщении #1202919 писал(а):
Если верна теорема Кука. А она не верна, если надо учитывать вот такое:
А Вы теперь утверждаете, что теорема Кука не верна? Давайте возьмем какое-нибудь конкретное доказательство, например, в книге В. Б. Алексеев "Введение в теорию сложности алгоритмов" (можно найти в интернете), и Вы скажете, где ошибка.

Я, к сожалению, совершенно не понимаю, о чем Вы говорите со своими $p_{\forall}(|S|, |s|)$ и $p_{\exists}(|S|)$, но раз у Вас теорема Кука ломается, значит, наверное, их не надо учитывать.

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


18/05/14
137
Москва
mihaild в сообщении #1202917 писал(а):
dmitgu, тогда явно выпишите, пожалуйста, какие у какого алгоритма на каком множестве ограничение на время работы.

На самом деле это как раз та задача, которую я строю в своей теореме :) Только в ней есть ещё пара частей у слова. Итого:

$d$, $t$, $S$, $s$

Для множества

$d$, $\overline{Anti(d, S) = 0}$, $S$, $s$ ограничение при проверке -
$p_{\exists}(|d|, |S|)$

А общее ограничение при проверке - $p_{\forall}(|d|, |t|, |S|, |s|)$

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


16/07/14
1272
Москва
Xaositect в сообщении #1202920 писал(а):
А Вы теперь утверждаете, что теорема Кука не верна?
Давно уже.
dmitgu в сообщении #1201355 писал(а):
КНФ - не является $\mathbb{NP}$-полной задачей


У меня есть гипотеза: dmitgu хочет фиксированный полиномиальный алгоритм, который пару (полиномиальная недетерменированная машина Тьюринга, вход) сводит к $3-SAT$.

(такого скорее всего наверняка нет, если $NP=coNP$, то точно нет, но это совершенно другая задача)

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


18/05/14
137
Москва
Xaositect в сообщении #1202920 писал(а):
А Вы теперь утверждаете, что теорема Кука не верна?


Не, с самого начала :-)
Xaositect в сообщении #1202920 писал(а):
о чем Вы говорите со своими $p_{\forall}(|S|, |s|)$ и $p_{\exists}(|S|)$


Предыдущий ответ для mihaild - об этом. Подмножество языка, на котором проверка неполиномиально быстрее, чем во всём. Помните, Вы ещё меня спрашивали, а точно ли алгоритм "Эдип" с программой в $d$ не сможет доказать $AntiOed_S() = 0$ ? Как раз случай игнорирования доказательства и аргумента $s$ - проверке заранее известно, что результат будет - 0. Вот для частного подмножества теорема Кука и не учитывает ограничение. Одной КНФ недостаточно - надо выбирать, не попадаешь ли ты в "скоростное" подмножество.

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


16/07/14
1272
Москва
dmitgu, что такое "ограничение при проверке"?
Выпишите, пожалуйста, явно:
-все нужные вам алгоритмы вместе со списками аргументов
-свойства этих алгоритмов: на каком входе они что выдают
-ограничение на время, за которое они это делают

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


06/10/08
5772
dmitgu в сообщении #1202926 писал(а):
Не, с самого начала :-)
Так а где там ошибка в доказательстве?

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


18/05/14
137
Москва
Xaositect в сообщении #1202931 писал(а):
Так а где там ошибка в доказательстве?


Не учитывается возможность существования "скоростного подмножества". Если считать, что КНФ при её решении в $P$ будет решать и исходную задачу - в которой "скоростное подмножество" есть и решение там должно быть неполиномиально быстрее общего.

Добавлю принципиальное:
То есть - для разных алгоритмов-решений будут разные КНФ вообще говоря. А это - терм. Надо выбрать нужный КНФ для правильного решения данного алгоритма-решения. А это не сводится к логике высказываний. Тут нужна индивидная переменная d

"Сводимость" к КНФ подразумевает ведь и сводимость решения к $P$ - если оно найдется?
А в исходной задаче я уже описывал возможную ситуацию:

dmitgu в сообщении #1202883 писал(а):
Интересно узнать:
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?


mihaild в сообщении #1202927 писал(а):
dmitgu, что такое "ограничение при проверке"?
Выпишите, пожалуйста, явно:
-все нужные вам алгоритмы вместе со списками аргументов
-свойства этих алгоритмов: на каком входе они что выдают
-ограничение на время, за которое они это делают


Не, сейчас не могу. Отчёты надо делать. Может позже. На будущее - я же вроде формулировал уже:

dmitgu в сообщении #1201652 писал(а):
В предлагаемом языке «слову» соответствует теорема $t$, предельный размер доказательства для неё в 2-х представлениях $S$ и $s$, и аргумент долга (текст некоторого алгоритма-решения) $d$. Слово считается подтвержденным (существует «сертификат»), если длина строки $s$ равна числу $S$, имеется доказательство $y$ размером до $S$, и если теорема не равна утверждению $\overline{Anti(d, S) = 0}$ - это утверждение построено так, что алгоритм $d$ заведомо не может найти «сертификат» для него.

Скорость работы алгоритма проверки разная для разных случаев. Если имеет место $\overline{Anti(d, S) = 0}$, то полиномиальное ограничение на время работы $p_{Anti}(|d|, |S|)$ – что неполиномиально меньше чем у «общего» $Sph(d, t, S, s, y)$, чей ограничивающий полином – $p(|d|, |s|)$. Так как $|S|$ неполиномиально меньше, чем $|s|$.

Вы понимаете, что у нас есть 2 (Два) полиномиальных ограничения на время работы? Для задачи в целом он больше (дольше), а для подзадачи $Sph(d, \overline{Anti(d, S) = 0}, S, s, y)$ – он неполиномиально меньше. Меньшее может входить в большее, поэтому подзадача соответствует «общей» задаче и её полиномиальному ограничению, но для корректного «Эдипа» при решении вопроса о $\overline{Anti(d, S) = 0}$ «существует» такая задача из класса $NP$, которая неполиномиально быстрее «общей». И не выдать соответствующий быстрый ответ – значит, быть неспособным свести эту подзадачу из класса $NP$ к классу $P$.

А выдать быстро – значит, утратить соответствие (равенство результатов) между решаемой тобой задачей, соответствующей аргументу долга $\overline{Oed(\overline{Sph(..., ..., ..., ..., ...)}, \overline{-}, ..., ..., ...)}$ и такой же задачей, но в которой иной лишь аргумент долга – равный $\overline{-}$.

Я строю задачу, в которой любые алгоритмы-решения могут решать только «свои» задачи – потому что алгоритм-решение соответствует некоторой части «слова» разбираемого «языка». Но существенным (с иным результатом и/или ограничением на время работы проверки) этот нюанс становится лишь на утверждениях типа $\overline{Anti(d, S) = 0}$.

То есть – возврат 0 «Эдипом» при поиске сертификата для $\overline{Anti(d, S) = 0}$ – соответствует «языку». Хоть «Эдип» ищет доказательство для «слова» с теоремой $\overline{Anti(d, S) = 0}$ и аргументом долга
«объективно»,

но его работа соответствует аргументу долга
«Эдип с аргументом долга «объективно»».

Потому что дело не в том, для какого аргумента долга он ищет, а в том, «кто» ищет. Аргумент долга «Сфинкса» (то есть элемент слова в предлагаемом «языке») должен соответствовать фактам а не аргументу долга внутри «Эдипа».Так как: «Но словам ведь соответствуют понятия» (c) «Фауст». А частью «слова» у нас является алгоритм-решение с тем, что у него подставлено в качестве аргумента долга, а не то, что у него подставлено – независимо от самого алгоритма-решения.

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


06/10/08
5772
У нас с Вами, к сожалению, нет общего языка, на котором мы разговариваем. Давайте Вы начнете с начала, определите снова всех Ваших Эдипов со Сфинксами, и покажете, как они соотносятся с общепринятыми определениями $\mathbf{NP}$.

Давайте установим некоторый фундамент:
- мы знаем, что такое машина Тьюринга и как кодировать машины и состояния машин словами. Код любого состояния машины меньше по длине, чем код самой машины.
- мы знаем, что такое время работы машины на заданном входном слове.
- у нас есть универсальная машина, которая получает на вход слово $m\sharp w\sharp 1^t$, где $m$ - код машины, $w$ - слово, и выдает результат вида $z\sharp u$. Результат расшифровывается так: после $t$ шагов вычисления машины с кодом $m$ на входе $w$ она находится в состоянии с кодом $z$, а на ее ленте ленте находится слово $u$. Время работы универсальной машины ограничено полиномом от длины входного слова $m\sharp w\sharp 1^t$.

-- Чт мар 23, 2017 17:49:11 --

dmitgu в сообщении #1202935 писал(а):
Не учитывается возможность существования "скоростного подмножества". Если считать, что КНФ при её решении в $P$ будет решать и исходную задачу - в которой "скоростное подмножество" есть и решение там должно быть неполиномиально быстрее общего.

"Сводимость" к КНФ подразумевает ведь и сводимость решения к $P$ - если оно найдется?
Не понимаю. Есть много алгоритмов решения $\mathrm{SAT}$, и у многих из них есть бесконечные множества КНФ, на которых они работают полиномиальное время. Это ничего не говорит нам о плохих случаях.

Вы возможно, как-то неправильно понимаете сводимость. Сводимость языка $L$ к $\mathrm{SAT}$ - это вот что: у нас есть функция $f$, вычисляемая за полиномиальное время. Если $w \in L$, то $f(w)$ есть выполнимая КНФ, а если $w\notin L$ - то $f(w)$ есть невыполнимая КНФ. Теорема Кука говорит, что для любого языка из $\mathbf{NP}$ есть такая функция. Для каждого языка такая функция своя, и для каждого языка таких функций много - нам это неважно, нас интересует существование хотя бы одной.

Понятно, что если у языка $L$ есть какое-то хорошее подмножество, для которого есть быстрый алгоритм, то $f$ может посылать его в какое-то хорошее множество КНФ, для которого есть быстрый алгоритм. А может и не посылать - это неважно, нас все равно интересуют только самые плохие слова для каждой длины.

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

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



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

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


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

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