Ошибки в теории вычислимости

[Xaositect]

Андрей АK в сообщении #286942 писал(а):

Функция, заданная бесконечным степенным рядом, вычислима или нет?

Некоторые вычислимы, некоторые нет.
Вы, кстати, о действительных функциях говорите? Там свои заморочки (вычислимость с заданной точностью, алгебраические модели, оракульные модели, конструктивные действительные числа). давайте сначала с натуральными разберемся.

[Андрей АK]

Xaositect в сообщении #286944 писал(а):

Андрей АK в сообщении #286942 писал(а):

Функция, заданная бесконечным степенным рядом, вычислима или нет?

Некоторые вычислимы, некоторые нет.
Вы, кстати, о действительных функциях говорите? Там свои заморочки (вычислимость с заданной точностью, алгебраические модели, оракульные модели, конструктивные действительные числа). давайте сначала с натуральными разберемся.

И как вы её охарактеризуете по "степени невычислимости"?
Сколько сложностей ради поддержания ошибки в определении.

Xaositect в сообщении #286941 писал(а):

Андрей АK в сообщении #286930 писал(а):

Возможно доказательство P<>NP лежит как раз в этом направлении...

Вряд ли, ибо в постановке проблемы речь идет о завершающихся алгоритмах.

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

[Xaositect]

Андрей АK в сообщении #286946 писал(а):

И как вы её охарактеризуете по "степени невычислимости"?

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

Андрей АK в сообщении #286946 писал(а):

Не путайте - "завершающиеся" - не значит "конечные".

http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf

-- Ср фев 10, 2010 16:30:45 --

Андрей АK в сообщении #286946 писал(а):

Вообще - алгоритм обратной к "сложной" функции - есть "прообраз" бесконечного алгоритма - т.е. алгоритм максимальной сложности из всех, ограниченных размером N.

Поясните

[Ales]

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

[Андрей АK]

Xaositect в сообщении #286947 писал(а):

Андрей АK в сообщении #286946 писал(а):

Вообще - алгоритм обратной к "сложной" функции - есть "прообраз" бесконечного алгоритма - т.е. алгоритм максимальной сложности из всех, ограниченных размером N.

Поясните

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

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

Итак, пусть у нас есть пронумерованное, конечное множество алгоритмов.
Строим алгоритм , который знает все номера алгоритмов из нашего множества и одновременно его номер (случайно?) присутствует среди списка номеров (т.е. является членом нашего множества).

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

Но для этого надо, чтоб среди множества алгоритмов, присутствовали ВСЕ варианты нумерации самих себя ... количество которых ,как известно , равно факториалу от общего количества алгоритмов.

Но N! всегда больше N (если N>2)

Итак, и для конечных множеств алгоритмов нельзя построить алгоритм, знающий все номера и одновременно входящий в множество, но зато мы получили представление о NP сложности.

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

Т.е. если некая задача использует конечный набор алгоритмов для своей работы, то обратная задача не может присутствовать среди этих алгоритмов и к тому же она должна быть в N! раз сложнее.

В общем где-то в этом направлении.

[Xaositect]

Андрей АK в сообщении #286972 писал(а):

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

Вы что-то путаете. Номер алгоритма эффективно вычисляется по его описанию.

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

-- Ср фев 10, 2010 18:02:44 --

Все равно ничего не понимаю.
У Вас там фигурирует некая NP-полная задача, я не понимаю ее формулировки.
Учтите, что понятие NP-полной задачи формулируется только для задач типа "да-нет".

[Ales]

А что Автор понимает под термином

Андрей АK в сообщении #286972 писал(а):

NP сложная задача

?
Тоже что-то свое?

Да и принятое определение "NP сложная задача" - немного странное. Что-то в нем не научное, полагаю.

Задача, которую можно решить за полиномиальное время, если ответ будет подсказан

[Xaositect]

Ales в сообщении #286982 писал(а):

Да и принятое определение "NP сложная задача" - немного странное. Что-то в нем не научное, полагаю.

NP-hard
Не уверен, что автор правильно понимает этот термин, но он есть.
Означает, что к этой задаче полиномиально сводится любая задача из NP.

-- Ср фев 10, 2010 18:27:06 --

Xaositect в сообщении #286974 писал(а):

У Вас там фигурирует некая NP-полная задача, я не понимаю ее формулировки.
Учтите, что понятие NP-полной задачи формулируется только для задач типа "да-нет".

Странно, мне показалось, что я увидел в посте Андрея АК термин NP-полная, а там его нет.
Извиняюсь.
Зато есть термин NP-сложная, но я все равно не вкурил, что за задача имеется в виду.

[Андрей АK]

Xaositect в сообщении #286985 писал(а):

Странно, мне показалось, что я увидел в посте Андрея АК термин NP-полная, а там его нет.
Извиняюсь.
Зато есть термин NP-сложная, но я все равно не вкурил, что за задача имеется в виду.

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

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

[Ales]

Xaositect в сообщении #286985 писал(а):

Означает, что к этой задаче полиномиально сводится любая задача из NP.

Но разве это не определение NP-полной задачи?
Я так помню: есть задачи NP-сложные (трудные) и часть из них NP - полные. Если решить NP-полную задачу (научиться проверять на тавтологию дизьюнктивную форму), получишь решение сразу всех остальных задач. А NP-сложные задачи - это задачи обратные к полиномиальным, но почему-то определены они по другому. Или не так?

[Xaositect]

Андрей АK в сообщении #286988 писал(а):

NP сложная задача - это я представляю себе такую задачу, сложность которой (количество инструкций для алгоритма) возрастает как N! - а это максимально возможная сложность для вообще любой задачи из N бит, поскольку это сложность переборного алгоритма, а перебором решается вообще любая задача.

К сведению: сложность алгоритма, решающего задачу определения доказуемости формулы арифметики Пресбургера (арифметики сложения) не может быть меньше $2^{2^{cn}}$, где $n$-длина формулы, $c$ - некоторая константа. Это значительно превышает факториал.

-- Ср фев 10, 2010 18:44:48 --

Ales в сообщении #286991 писал(а):

Но разве это не определение NP-полной задачи?

NP-полная задача - это задача, одновременно являющаяся NP-трудной и принадлежащая NP.
http://en.wikipedia.org/wiki/File:P_np_ ... p-hard.svg

-- Ср фев 10, 2010 18:48:10 --

Кроме того, понятие NP-сложности определяется не только для задач типа "да-нет", но и для функций.

[Ales]

Андрей АK в сообщении #286988 писал(а):

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

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

Кажется, Вы немного смешали разные науки в одну: вопросы сложности реальных алгоритмов и теоретических.
Все задачи NP решаются перебором $2^N$ вариантов. Реально перебор неосуществим, и в то же время его теоретическая возможность не позволяет получить отрицательный результат $P\neq NP$.

[Xaositect]

Ales в сообщении #287000 писал(а):

Все задачи NP решаются перебором $2^N$ вариантов. Реально перебор неосуществим, и в то же время его теоретическая возможность не позволяет получить отрицательный результат $P\neq NP$.

Немного не так. Во-первых, не $2^N$, а $2^{\mathrm{poly}(N)}$, но это так, придирки.
Для того, чтобы доказать, что $\mathbf{P}\neq \mathbf{NP}$, нужно доказать, что перебор в некотором смысле обязателен, что не существует какого-то другого способа, позволяющего решать задачу за полином от $N$.

[Ales]

Xaositect в сообщении #286993 писал(а):

NP-полная задача - это задача, одновременно являющаяся NP-трудной и принадлежащая NP.

ОК, понятно. Я не думал, что есть какие-то задачи не NP, и неправильно понимал, под NP-сложными те задачи, которые называют просто NP. Научное определение: NP-сложная (трудная) задача может и не быть сама из NP (то есть она еще сложнее), но если ее решить то все задачи из NP будут решены.
А есть ли реальные задачи сложнее чем NP?

Xaositect в сообщении #287001 писал(а):

Для того, чтобы доказать, что , нужно доказать, что перебор в некотором смысле обязателен, что не существует какого-то другого способа, позволяющего решать задачу за полином от .

Я, наверное, неправильно выразил свою следующую мысль: поскольку всегда есть быстрый алгоритм подстановки правильного ответа, нельзя доказать что $P \neq NP$. Каждая задача либо имеет, либо не имеет решения, если у нее есть решение, то есть быстрый способ проверки и алгоритм подстановки, если же Вы смогли доказать что у нее нет решения, то она тоже таким образом решена. Поэтому есть либо проблемы решенные (класса $P$), либо про которые ничего неизвестно (класса $NP$).

[Андрей АK]

Xaositect в сообщении #286993 писал(а):

К сведению: сложность алгоритма, решающего задачу определения доказуемости формулы арифметики Пресбургера (арифметики сложения) не может быть меньше $2^{2^{cn}}$, где $n$-длина формулы, $c$ - некоторая константа. Это значительно превышает факториал.

Ну да , ошибся, когда писал - думал про другое и написал не то.

Но собственно, я уже все сказал.

Я тут собираю небольшую коллекцию математических ошибок (с моей точки зрения), и эта одна из них.

Я так понял, единственное возражение такое - что это мол раз принято, что алгоритмы конечные, значит конечные, а все остальное - побоку.

Ну и ладно. Так и запишем.