Вычислимость и сложность

[alleut]

1) Существует ли алгоритм, проверяющий, работает данная программа полиномиальное время?
Кажется, что нет. Иначе бы без проблем могли установить, как соотносятся классы P и NP.
Но как это доказать?

2)Приведите пример двух непересекающихся неперечислимых множества.
Рассмотрим счётную последовательность всех перечислимых множеств $A_1, A_2,...A_p...$
Может, тогда построим первое неперечислимое множество следующим образом: $N_1=\{\min(A_1)+1, \min(A_2)+1,...,\min(A_p)+1...\}$, а второе $N_2=\{\min(A_1)+2, \min(A_2)+2,...,\min(A_p)+2...\}$, откидывая те числа, которые встречались в $N_1$

3) (Верещагин, Шень, №13) Покажите, что для всякой вычислимой функции $f$ существует вычислимая функция, являющаяся псевдообратной к $f$ в следующем смысле: область определения $g$ совпадает с областью значений $f$, и при этом $f(g(f(x))) = f(x)$ для всех $x$, при которых $f(x)$ определено.
Мы знаем, что функция вычислима тогда и только тогда, когда её график $F = \{<x, y> | f(x)=y\}$ (если определено). Тогда в качестве g можно взять функцию, которая сопоставляет каждому $y$ из проекции $F$ $x$, такой, что $f(x)=y$

4) Приведите пример неразрешимого множества $A \subseteq \ineq N\times N$, такого, что все его горизонтальные и вертикальные сечения разрешимы.
Ну, может быть, пронумеровать все разрешимые множества $p_0, p_1,...$ составить из них неким способом универсальное $P(x,n)$ и показать, что оно неразрешимо?

5) Докажите, что существует язык, который можно распознать с памятью $2^n$, но не с памятью $n$
Распознать $=$ разрешить? И где можно узнать, что такое "распознать с памятью"?

[Xaositect]

alleut в сообщении #625764 писал(а):

1) Существует ли алгоритм, проверяющий, работает данная программа полиномиальное время?
Кажется, что нет. Иначе бы без проблем могли установить, как соотносятся классы P и NP.
Но как это доказать?

Ну тут стандартно - сводите к проблеме останова. Вам дана пара из программы $n$ и входных данных $x$. Постройте программу $n'$, которая работает полиномиальное время, если $n$ останавливается на $x$, и неполиномиальное, если нет.
PS. Разрешимости этого, кстати, недостаточно для решения $P?=NP$. Там надо доказать или опровергнуть, что все программы для решения NP-полной задачи работают не полиномиально.

alleut в сообщении #625764 писал(а):

2)Приведите пример двух непересекающихся неперечислимых множества.

А почему после выкидывания из $N_2$ элементов $N_1$ останется неперечислимое множество? Вы не доказали.
Почитайте лучше классическую конструкцию рекурсивно неотделимых множеств, в том же Верещагине-Шене.

alleut в сообщении #625764 писал(а):

3) (Верещагин, Шень, №13)

Верно. Для закрепления можете выразить функцию $g$ через $f$ с помощью композиции и оператора $\mu$.

alleut в сообщении #625764 писал(а):

4) Приведите пример неразрешимого множества , такого, что все его горизонтальные и вертикальные сечения разрешимы.

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

alleut в сообщении #625764 писал(а):

Распознать разрешить? И где можно узнать, что такое "распознать с памятью"?

Да, распознать=разрешить. Про память в учебнике по теории сложности. Например, Кузюрин-Фомин. "Эффективные алгоритмы и сложность вычислений", \S 6.1.2 (там это называется "пространственная сложность"),

[alleut]

Цитата:

Постройте программу , которая работает полиномиальное время, если останавливается на , и неполиномиальное, если нет.

Идея в целом понятна, но... Предположим, мы построим такую программу $n'$. С учётом построения она точно будет работать неполиномиальное время на входе $n$. Но что это может сказать об исходной $n$? Или сам "код" $n'$ должен быть таким, чтобы сразу всё ясно стало?

Цитата:

Почитайте лучше классическую конструкцию рекурсивно неотделимых множеств, в том же Верещагине-Шене.

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

Цитата:

Проще взять график возрастающей невычислимой функции.

Функция невычислима, поэтому весь график неразрешим. Но разве принадлежность сечению можно будет проверить, если функция невычислима?

Цитата:

Докажите, что существует язык, который можно распознать с памятью $2^n$, но не с памятью $n$

$n$ - длина слова. Ну, если язык в языке слова из нулей и единиц, то с памятью $2^n$ можно просто составить все возможные варианты и сравнить их с самим языком.

[Xaositect]

alleut в сообщении #626044 писал(а):

Идея в целом понятна, но... Предположим, мы построим такую программу $n'$. С учётом построения она точно будет работать неполиномиальное время на входе $n$. Но что это может сказать об исходной $n$? Или сам "код" $n'$ должен быть таким, чтобы сразу всё ясно стало?

Давайте разберем подробнее. Это стандартный прием, Вам его надо понимать.
Мы хотим доказать неразрешимость множества полиномиальных программ, то есть, что не существует вычислимой функции $A(m)$ такой, что $A(m) = 1$ тогда и только тогда, когда программа $m$ имеет полиномиальную асимптотику.
У нас есть набор стандартных неразрешимых задач. У Вас в этом наборе, скорее всего, только пара вариаций проблемы останова, она то нам и нужна. Мы знаем, что не существует вычислимой функции $H$ такой, что $H(n, x) = 1$ тогда и только тогда, когда программа $n$ останавливается на входе $x$.
Нам надо эти две задачи как-то связать. Как именно? Для того, чтобы доказать, что нельзя вычислить $A$, можно попробовать доказать, что, умея вычислять $A$, мы сумеем вычислить и $H$. Это идея сводимости, помедитируйте над ней немного.
Как мы можем это сделать? Мы можем попробовать определить вычислимую функцию $f(n,x)=m$, которая переводит пары, для которых $H(n,x) = 1$, в программы, для которых $A(m)=1$ и наоборот. Тогда, умея вычислять $A(m)$, мы сможем вычислить и $H(n,x) = A(f(n,x))$, чего мы сделать никак не можем. Значит, $A$ невычислима.

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

Цитата:

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

Ой, это меня немного переклинило. Вам же нужны неперечислимые множества. Тут можно пойти таким путем: доказать, что в любом бесконечном разрешимом множестве есть неперечислимое подмножество.

alleut в сообщении #626044 писал(а):

Функция невычислима, поэтому весь график неразрешим. Но разве принадлежность сечению можно будет проверить, если функция невычислима?

Какие будут сечения у такого графика?

alleut в сообщении #626044 писал(а):

- длина слова. Ну, если язык в языке слова из нулей и единиц, то с памятью можно просто составить все возможные варианты и сравнить их с самим языком.

1. Как это связано с распознаванием языка? 2. При чем тут память, все вариант можно перебрать, имея $\Theta(n)$ памяти, но $\Theta(2^n)$ времени.

[alleut]

1)Если программа работает полиномиальное время, то она должна за полиномиальное время выдавать результат для любого входа, в т. ч. для своего номера.
Получается, такая программа должна останавливаться на своём входе, и для полиномиальных алгоритмов мы можем решить проблему остановки.
Как-то так?

Цитата:

Какие будут сечения у такого графика?

Или набор значений, соответствующих одному аргументу,
или набор аргументов, соответствующих одному значению.

Цитата:

2. При чем тут память, все вариант можно перебрать, имея $\Theta(n)$ памяти, но $\Theta(2^n)$ времени.

Тогда мне и вовсе суть задачи не понятна, если это можно сделать за $\Theta(n)$ памяти.
Задача "хочет" узнать алгоритм, который определяет, входит ли слово длины $n$ в язык, и использует при этом не менее $n$ и не более $2^n$ ячеек на ленте машины Тьюринга.
В такого рода формулировках задач затраты по времени любые или нет? Если любые и пространственные затраты можно "компенсировать" временем, то что?

[Xaositect]

alleut в сообщении #626111 писал(а):

1)Если программа работает полиномиальное время, то она должна за полиномиальное время выдавать результат для любого входа, в т. ч. для своего номера.
Получается, такая программа должна останавливаться на своём входе, и для полиномиальных алгоритмов мы можем решить проблему остановки.
Как-то так?

Полиномиальная программа по определению останавливается. Перечитайте все еще раз.

alleut в сообщении #626111 писал(а):

Или набор значений, соответствующих одному аргументу,
или набор аргументов, соответствующих одному значению.

Угу. И будут ли эти множества разрешимыми?

alleut в сообщении #626111 писал(а):

В такого рода формулировках задач затраты по времени любые или нет? Если любые и пространственные затраты можно "компенсировать" временем, то что?

Затраты по времени любые. Но не любые пространственные затраты можно компенсировать временем, и как раз в этом и состоит суть задачи.

[alleut]

Цитата:

Как мы можем это сделать? Мы можем попробовать определить вычислимую функцию $f(n,x)=m$, которая переводит пары, для которых $H(n,x) = 1$, в программы, для которых $A(m)=1$ и наоборот. Тогда, умея вычислять $A(m)$, мы сможем вычислить и $H(n,x) = A(f(n,x))$, чего мы сделать никак не можем. Значит, $A$ невычислима.

$f(n,x)=n$ ?

Цитата:

Угу. И будут ли эти множества разрешимыми?

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

[Xaositect]

alleut в сообщении #626266 писал(а):

Цитата:

Как мы можем это сделать? Мы можем попробовать определить вычислимую функцию $f(n,x)=m$, которая переводит пары, для которых $H(n,x) = 1$, в программы, для которых $A(m)=1$ и наоборот. Тогда, умея вычислять $A(m)$, мы сможем вычислить и $H(n,x) = A(f(n,x))$, чего мы сделать никак не можем. Значит, $A$ невычислима.

$f(n,x)=n$ ?

Ну пусть $n$ - это неполиномиальная программа, реализующая тотальную функцию. Подходит ли Ваша функция $f$ под условие "$f(n,x)=m$, которая переводит пары, для которых $H(n,x) = 1$, в программы, для которых $A(m)=1$ и наоборот."?

Цитата:

Цитата:

Угу. И будут ли эти множества разрешимыми?

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

Нам не нужно проверять принадлежность точки графику. Нам нужно проверять принадлежность точки сечению. Если $f(x) = y$, то сечение графика по $x$ будет содержать одну точку $y$, то есть оно даже не просто разрешимо, а даже конечно.

[alleut]

Xaositect, спасибо за помощь, я, кажется, разобрался.