2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 8, 9, 10, 11, 12, 13, 14 ... 26  След.
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение18.03.2017, 00:19 
Аватара пользователя


18/05/14
215
Москва
mihaild в сообщении #1201353 писал(а):
Непонятно - вы предлагаете вместо задачи "существует ли выполняющий набор для данной КНФ" решать задачу "выдает ли данный алгоритм выполняющий набор для данной КНФ"?


Я разбираю не КНФ. И к КНФ "авторизуемые задачи" не сводятся:
dmitgu в сообщении #1201323 писал(а):
4.6. И не сводится потому, что получая алгоритм проверки – алгоритм-решение должен «понять», нет ли «персональной информации» для него. А это уже выбор – на основе терма. А к логике высказывания индивидные переменные и символы не сводятся.


КНФ - не является $\mathbb{NP}$-полной задачей, если "авторизуемые задачи" являются задачами из класса $\mathbb{NP}$.

Работа алгоритма имеет свое представление в языке - если это язык теории Пеано. И определённые "сертификаты" алгоритм не может сгенерировать в принципе. И для любого алгоритма есть такие нерешаемые задачи. Есть "слова", которые данный конкретный алгоритм заведомо не может подтвердить сертификатом. Если речь идёт о детерминированных алгоритмах - а именно их решение нас и интересует, чтобы свести $\mathbb{NP}$ к $\mathbb{P}$.

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


16/07/14
8355
Цюрих
dmitgu в сообщении #1201355 писал(а):
КНФ - не является $\mathbb{NP}$-полной задачей, если "авторизуемые задачи" являются задачами из класса NP.
О как. Т.е. вы доказываете что-то не про известный класс $NP$, а про какой-то другой? Потому что $3-SAT$ является широко известным примером $NP$-полной задачи. Или в доказательстве ошибка?)

Если вы доказываете что-то про другой класс - то назовите его, пожалуйста как-то иначе (во избежание путаницы), и сформулируйте его определение максимально кратко.
(в идеале - после формулировки определения еще сказать, зачем этот класс этот нужен)

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


18/05/14
215
Москва
mihaild в сообщении #1201356 писал(а):
Т.е. вы доказываете что-то не про известный класс $NP$, а про какой-то другой? Потому что $3-SAT$ является широко известным примером $NP$-полной задачи. Или в доказательстве ошибка?


Да, в доказательстве ошибка - имхо - именно поэтому я хочу обсудить такой неожиданный вывод и понять - может это у меня ошибка.

А ошибка состоит в том - на мой взгляд, что в "слове" может быть инфа о алгоритме, который ищет сертификат. И в зависимости от алгоритма результаты могут быть разные.

Я же пытаюсь реализовать программу Гильберта, а когда он и другие (Гёдель в частности) стал рассматривать доказательства о доказательствах - результат получился неожиданный. И я рассматриваю такие "сертификаты", которые строятся на базе доказательств. А в качестве "слов" беру утверждения теории 1-го порядка.

А теории 1-го порядка в состоянии "представлять" алгоритмы, их работу и утверждения о них.

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


16/07/14
8355
Цюрих
dmitgu в сообщении #1201361 писал(а):
Да, в доказательстве ошибка
"Ну так с этого надо было начинать!"
Это гораздо более важный результат, чем равенство или неравенство $P$ и $NP$ (с его использованием можно закрыть все решить все открытые проблемы разом).

dmitgu в сообщении #1201361 писал(а):
А ошибка состоит в том - на мой взгляд, что в "слове" может быть инфа о алгоритме, который ищет сертификат
Так, для начала - формальные определения понятия "алгоритм", "машина Тьюринга", "время работы", "классы $P$ и $NP$" вам хорошо известны?

Доказательство теоремы Кука заключается примерно в том, что для любой МТ и любого числа $n$ можно построить "кодирующую" МТ, которая по слову $X$ за полиномиальное от длины $X$ время генерирует КНФ (длина автоматически получается полиномиальной от длины $X$), которая выполнима тогда и только тогда, когда МТ принимает $X$ за время, не превосходящее $|X|^n $. Что и означает, что задача $SAT$ является $NP$-полной.
(на самом деле генерировать формулу можно даже равномерно по всем МТ - получится полиномиальная по длине кода МТ и экспоненциальная по $n$ сложность - но это не нужно)

Вы не согласны с возможностью построения такой МТ? (можете привести конкретную пару МТ, $n$, для которых такую "кодирующую" МТ построить нельзя?) Или с чем?

dmitgu в сообщении #1201361 писал(а):
И я рассматриваю такие "сертификаты", которые строятся на базе доказательств.
Одна из важных идей в этой области - сертификат может быть устроен как угодно.

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


18/05/14
215
Москва
mihaild в сообщении #1201365 писал(а):
Доказательство теоремы Кука заключается примерно в том, что для любой МТ и любого числа $n$ можно построить "кодирующую" МТ, которая по слову $X$ за полиномиальное от длины $X$ время генерирует КНФ (длина автоматически получается полиномиальной от длины $X$), которая выполнима тогда и только тогда, когда МТ принимает $X$ за время, не превосходящее $|X|^n $


Да, а если есть отдельная часть $X$, неполиномиально меньшая, чем сам $X$? :) И алгоритм проверки «Сфинкс», для некоторых алгоритмов-решений создающий свою подзадачу на основе именно части $X$, а не целого?

Вот смотрите, разберём переход от описания для слов:

$\operatorname{Sph}(\overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ..., ..., ...)}, \overline{-}, ..., ..., ...)}, t_{Oed, S}, S, s, y) = 0$

или

$\operatorname{Sph}(d_{Oed}, t_{Oed, S}, S, s, y) = 0$

к описанию подзадачи.

2ой частью слова тут является утверждение: $t_{Oed, S} = \overline{\operatorname{AntiOed_S}() = 0}$.

А 1ой частью слова является тут «избранный» алгоритм-решение «Эдип» с конкретным аргументом долга:

$d_{Oed} = \overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ..., ..., ...)}, \overline{-}, ..., ..., ...)}$

И для $\operatorname{Oed}(\overline{\operatorname{Sph}(…, …, …, …, …)}, d_{Oed}, t_{Oed, S}, S, s)$ нет проблем выдать $0$ – как и для других , $\operatorname{NotOed}(\overline{\operatorname{Sph}(…, …, …, …, …)}, d_{Oed}, t_{Oed, S}, S, s)$ но речь-то о:

$\operatorname{Oed}(\overline{\operatorname{Sph}(…, …, …, …, …)}, \overline{-}, t_{Oed, S}, S, s)$

ведь именно о нём речь у «Сфинкса» с его нулём: $\operatorname{Sph}(d_{Oed}, t_{Oed, S}, y, S, s) = 0$.

А на $\operatorname{NotOed}(\overline{\operatorname{Sph}(…, …, …, …, …)}, \overline{-}, t_{Oed, S}, S, s)$ предыдущая формула для «Сфинкса» не распространяется. Для него - $\operatorname{Sph}(\overline{-}, t_{Oed, S}, y, S, s) = 0$. И ему (не-Эдипу) остаётся «довольствоваться» обычным временем работы «Сфинкса», полиномиальным от размера всего $|X|$ (от |s| в частности).

Вот тут-то и возникает терм и невозможность свести выражение к логике высказываний (к КНФ). И для конкретно этих параметров полином для времени работы

$\operatorname{Sph}(d_{Oed}, t_{Oed, S}, y, S, s) = 0$

будет зависеть от $|S|$, но не от $|s|$. И от $|y|$ не будет зависеть. А отличие между $|S|$ и $|s|$ - неполиномиально большое (количество десятичных цифр и само число). Так я строю свою задачу в следующем разделе.

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


16/07/14
8355
Цюрих
Выписывайте, пожалуйста, все ваши "аргументы долга" и алгоритмы так, чтобы можно было понять, чему это соответствует в терминах машин Тьюринга и языков.
dmitgu в сообщении #1201411 писал(а):
$\operatorname{Sph}(\overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ..., ..., ...)}, \overline{-}, ..., ..., ...)}, t_{Oed, S}, S, s, y) = 0$
Что такое $Sph$ и $Oed$? Алгоритмы? Какие (что на вход, что на выход)? Что скрывается за многоточиями? Что означает надчеркивание? Что значат все используемые буквы?

dmitgu в сообщении #1201411 писал(а):
Да, а если есть отдельная часть $X$, неполиномиально меньшая, чем сам $X$?
Что такое "отдельная часть $X$"?
Формула строится примерно так: мы на каждый из $p(|X|)$ шагов выделяем переменные, которые будут кодировать конфигурацию МТ на очередном шаге. Дальше нам нужно записать, что начальная конфигурация - слово $X$, конечная - принимающая, и все переходы правильные. Никакого "разбора" что "внутри" $X$ нет (и формулы с разными $X$ одной и той же длины будут отличаться друг от друга только в небольшой части, говорящей про начальную конфигурацию).

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


18/05/14
215
Москва
mihaild в сообщении #1201419 писал(а):
Что такое $Sph$ и $Oed$? Алгоритмы? Какие (что на вход, что на выход)?

Алгоритм проверки:

$Sph(d, t, S, s, y)$ - аргументы "долга" (алгоритма-решения), теоремы, аргументы размера (наибольшая длина доказательства) в виде числа и строки "11...1" длиной $S$ (иначе Сфинкс вернёт $0$), $y$ - доказательство.

Разбираемый нами алгоритм-решение.

$Oed(a, d, t, S, s)$ - первый аргумент $a$ - программный текст алгоритма проверки (задача из $NP$). Дальше как в предыдущем

mihaild в сообщении #1201419 писал(а):
Что скрывается за многоточиями?

Вот (не всё):
dmitgu в сообщении #1201323 писал(а):
2.3. Пояснение к пункту 2.1 о способе подстановки аргументов в один алгоритм с получением другого алгоритма:

Алгоритм по превращению одного текста алгоритма в другой – с подставленным первым аргументом – можно изображать так: $Arg1(\overline{MyArg}, \overline{A(..., ...)})$. Мы использовали выше и продолжим использовать далее обозначения типа $B(\overline{A(..., ...)}, x), B(\overline{A(..., ...)}, ...)$ и т.п. Подразумевается, что таким образом мы используем какой-то стандартный известный способ по превращению алгоритма, зависящего от нескольких аргументов в некие другие алгоритмы – в которых часть аргументов (или даже все) исходного алгоритма уже подставлена. А можем передавать тексты алгоритмов и без подставленных аргументов, как, например $\overline{A(..., ...)}$.


mihaild в сообщении #1201419 писал(а):
Что означает надчеркивание?

Вот что:
dmitgu в сообщении #1201279 писал(а):
И по поводу обозначения – фрагмент из начала раздела 4 «Предварительное замечание о программе Гильберта для теории алгоритмов» -

На самом деле, алгоритм-решение должен получать текст программы алгоритма проверки и быть вида:

$M(\overline{L(x, y)}, x)$

Где $ \overline{L(x, y)}$ обозначает текст программы алгоритма проверки (на каком-то языке программирования), а не сам алгоритм. Именно такое обозначение для текста программ мы будем использовать и в дальнейшем.

mihaild в сообщении #1201419 писал(а):
Никакого "разбора" что "внутри" $X$

Да никто и не разбирает :) Это как с "сертификатом" - если его размер превышает полиномиальные ограничения - он отвергается алгоритмом проверки. И время на рассмотрение его "хвоста" даже не тратится.

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


16/07/14
8355
Цюрих
И что делает алгоритм $Sph$? Говорит, является ли $y$ доказательством чего-то про остальные аргументы - если да, то чего? Тот же вопрос про $Oed$.

dmitgu в сообщении #1201422 писал(а):
программный текст алгоритма проверки (задача из $NP$)
Не-не-не, задача из $NP$ - это язык, а не алгоритм.

Как именно будет выглядеть задача из $NP$, которая не сводится к $SAT$? "Множество слов, на которых $Sph$ и $Oed$ что-то там"?

По остальным обозначениям вроде пока понятно.

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


18/05/14
215
Москва
mihaild в сообщении #1201429 писал(а):
что делает алгоритм $Sph$? Говорит, является ли $y$ доказательством чего-то про остальные аргументы - если да, то чего? Тот же вопрос про $Oed$


Да, проверяет - доказывается ли $t$ доказательством y алгоритмом $d$ с учётом известных (для Сфинкса) ограничений на возможности $d$ - а доказательство в пределах длины $S$. Если длина строки $|s|$ меньше числа (не размера!) $S$ - то тоже негативный ответ. Если проверку не прошла - $0$. Прошла - $1$.

mihaild в сообщении #1201429 писал(а):
Не-не-не, задача из $NP$ - это язык, а не алгоритм.


Это как раз очень интересно :) В 1ом разделе я как раз разбираюсь, чего вообще понимают под задачей из класса $NP$. Штука - не формализованная и программа Гильберта для неё не проводилась. Вот чтоб "решить" - превратив задачу из $NP$ в задачу из $P$ - надо же передать текст некому алгоритму-решению. А текст чего? Я считаю - программный текст алгоритма проверки. И из него уже вычислять всякие полиномиальные ограничения. А что алгоритм проверки "ходит" парой с формулой на полиномиальное ограничение сертификата? А если формула не правильная? Математический класс не может зависеть от того, знаем мы или нет какое там полиномиальное ограничение. Задача из класса $NP$ вообще не имеет разрешимого способа распознания - потому что любое конечное время работы на единичной задаче не нарушает полиномиальность, но нельзя разрешить вопрос об остановке. Поэтому и принадлежность задачи классу $NP$ - неразрешимый вопрос.

Более того, в учебниках не сказано явно в какой модели интерпретации строится метаматематика в теории алгоритмов. В стандартной? Это когда на ленте машины Тьюринга число $11000$ представлено блоком из $11000$ единиц? Так никакую оценку по размерам и времени работы нельзя провести. Поэтому проблемы построения формализма в теории алгоритмов сейчас - огромные. И не я в этом виноват :) Я как раз считаю нужным и провожу - в меру своих сил - программу Гильберта. А без этого даже инструментов нет по решению проблем сложности в теории алгоритмов. Но чтоб всё сказать - это мне надо разделы 1 и 2 сюда запостить...

mihaild в сообщении #1201429 писал(а):
Как именно будет выглядеть задача из $NP$, которая не сводится к $SAT$


Вчерне я обозначил её раньше - когда пара:

алгоритм долга:
dmitgu в сообщении #1201411 писал(а):
$d_{Oed} = \overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ..., ..., ...)}, \overline{-}, ..., ..., ...)}$


и теорема:
dmitgu в сообщении #1201411 писал(а):
$t_{Oed, S} = \overline{\operatorname{AntiOed_S}() = 0}$.


оказывались информацией для возможностей поиска "Эдипа" в отношении пары:
$\overline{-}$ и той же теоремы. И шансы "Эдипа" по этой информации - нулевые.

Вот тут "фишка" - есть "персональная подсказка", которая неполиномиально быстрее "общего" алгоритма.

Да, "Эдип" должен "понимать", но это условность. А он в любом случае должен понимать условности - хотя бы язык, на котором записан программный код. И если он быстро ответит 0 (ноль) - не могу найти доказательство, то доказательство - будет! В пределах s. А если будет "тянуть время", то выйдет за рамки полиномиальности времени получения доступной ему инфы.

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


06/10/08
6422
dmitgu в сообщении #1201474 писал(а):
Это как раз очень интересно :) В 1ом разделе я как раз разбираюсь, чего вообще понимают под задачей из класса $NP$. Штука - не формализованная и программа Гильберта для неё не проводилась.
Вы, может быть, официальную формулировку института Клэя прочитаете?

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


18/05/14
215
Москва
Xaositect в сообщении #1201475 писал(а):
Вы, может быть, официальную формулировку института Клэя
прочитаете?


Нет. Английский и на бытовом уровне почти не знаю.

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


06/10/08
6422
Перевел определения:

Стивен Кук (перевод мой) писал(а):
Формально, элементами класса $\mathbf{P}$ являются языки. Пусть $\Sigma$ - конечный алфавит(то есть конечное непустое множество), содержащий по крайней мере 2 элемента, и $\Sigma^*$ - множество всех конечных слов в алфавите $\Sigma$. Язык в алфавите $\Sigma$ --- подмножество $\Sigma^*$. С любой машиной Тьюринга $M$ связан ее входной алфавит $\Sigma$. Для любого слова $w$ из $\Sigma^*$ существует вычисление машины $M$ на входе $w$. (Машина Тьюринга и вычисление определены формально в приложении.) Будем говорить, что $M$ принимает слово $w$, если в конце вычисления машина находится в принимающем состоянии. Таким образом, $M$ не принимает $w$, если вычисление завершается в отвергающем состоянии машины, или если процесс вычисления не завершается. Язык, распознаваемый машиной $M$ (обозначается $L(M)$) - это язык в алфавите $\Sigma$, определяемый как $L(M) = \{ w\in \Sigma^* \mid M \text{ принимает } w \}$. Обозначим $t_M(w)$ количество шагов вычисления $M$ на входе $w$ (см. приложение). Если вычисление не завершается, то $t_M(w) = \infty$. Для $n \in \mathbb{N}$ обозначим $T_M(n)$ время вычислений на слове длины $n$ в худшем случае, то есть $T_M(n) = \max \{t_M(w) \mid w \in \Sigma^n \}$, где $\Sigma^n$ - множество всех слов длины $n$ в алфавите $\Sigma$. Будем говорить, что машина $M$ работает полиномиальное время, если существует $k$ такое, что для любого $n$ верно $T_M(n) \leq n^k + k$. Теперь мы можем определить класс языков $\mathbf{P}$ как $$\mathbf{P} = \{L \mid L = L(M) \text{ для некоторой машины Тьюрина $M$, которая работает полиномиальное время}\}.$$
Обозначение $\mathbf{NP}$ расшифровывается как "nondeterministic polynomial time", поскольку этот класс изначально определялся в терминах недерминированных машин. Однако сейчас обычно дается эквивалентное определение, использующее понятие проверяющего отношения - бинарного отношения $R \subset \Sigma^* \times \Sigma_1^*$ для некоторых конечных алфавитов $\Sigma$ и $\Sigma_1$. Каждому такому отношению мы ставим в соответствие язык в алфавите $\Sigma \cup \Sigma_1 \cup \{\sharp\}$ определяемый как $$L_R = \{w \sharp y \mid R(w, y) \},$$ где символ $\sharp$ не принадлежит языку $\Sigma$. Будем говорить, что $R$ проверяется за полиномиальное время, если $L_R \in \mathbf{P}$. Определим класс языков $\mathbf{NP}$ следующим образом: язык $L$ в алфавите $\Sigma$ принадлежит $\mathbf{NP}$ если и только если существует $k \in \mathbb{N}$ и проверяемое за полиномиальное время бинарное отношение $R$ такие, что для любого слова $w \in \Sigma^*$ $$w \in L \Leftrightarrow \exists y\,(|y| \leq |w|^k \text{ и } R(w, y)),$$ где $|w|$ и $|y|$ - длины слов $w$ и $y$ соответственно.
Формулировка проблемы. Верно ли, что $\mathbf{P} = \mathbf{NP}$?

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


18/05/14
215
Москва
Спасибо за перевод.

Xaositect в сообщении #1201483 писал(а):
язык $L$ в алфавите $\Sigma$ принадлежит $\mathbf{NP}$ если и только если существует $k \in \mathbb{N}$ и проверяемое за полиномиальное время бинарное отношение $R$ такие, что для любого слова $w \in \Sigma^*$ $$w \in L \Leftrightarrow \exists y\,(|y| \leq |w|^k \text{ и } R(w, y)),$$


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

В результате задача начинает включать в себя множество подзадач - для разных алгоритмов-решений. И у некоторых подзадач (со "специальными" утверждениями) время проверки оказывается неполиомиально меньше, чем у общего алгоритма. И ответ о возможности найти ответ в таких специальных задачах для заданного алгоритма-решения - негативный. И это соответствует тому, что он действительно не может найти соответствующий "сертификат" (доказательство).

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


06/10/08
6422
Я, честно говоря, так и не понял, что все эти Ваши алгоритмы делают. Напишите формально, какой язык $L$ и какое отношение $R$ будут у Вашей "нехорошей" задачи?

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


16/07/14
8355
Цюрих
dmitgu в сообщении #1201474 писал(а):
доказывается ли $t$ доказательством y алгоритмом $d$ с учётом известных (для Сфинкса) ограничений на возможности $d$ - а доказательство в пределах длины $S$.
Вот это я не могу прочитать чисто синтаксически (кажется, предложение не согласовано). А все разумные попытки поправить приводят к неизвестным странным терминам типа "доказательство алгоритма".

dmitgu в сообщении #1201474 писал(а):
В 1ом разделе я как раз разбираюсь, чего вообще понимают под задачей из класса $NP$
А что разбираться? Язык принадлежит $NP$, если существует недетерменированная полиномиальная МТ, проверяющая его за полиномиальное время. Для арифметических языков (задаваемых формулой - в том числе всех перечислимых) это легко формализуется в арифметике, для произвольных - в любой теории, умеющей работать с произвольными подмножествами $\mathbb{N}$. Вполне возможно, что кто-то даже явно построил формулу.

"Проблема формализма" исключительно в том, что всем заинтересованным лицам понятно, как формализовывать дальше, чем обычно (вплоть до уровня множеств), и, поскольку это всем понятно, это никому не нужно.

Вообще, попробуйте почитать известные книги по алгоритмам и сложности (начать можно, например, с "Вялый, Китаев, Шень. Классические и квантовые алгоритмы" (первая часть)). И сравните их текст с вашим.
Все используемые термины надо определять. Что такое "информация для алгоритма в отношении пары", что такое "шансы по информации" и т.д.

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

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



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

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


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

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