Определение свойств программы (функции) по коду (формуле)

[Ales]

Можно ли по коду программы (булевой функции, алгоритма) определить ее свойства?

Например, булева функция отображает наборы из нулей и единиц в наборы из нулей и единиц такой же длины.
Можно ли по коду (формуле функции) определить будет ли это отображение взаимно-однозначным или нет?
Люди строят биекции (шифрователи) разными способами.
Зная как делать шифрователи, можно создавать для них коды,
но можно ли по коду, определить шифрователь это или нет.

Есть ли вообще какие либо свойства, которые можно определить по коду (формуле)?

Для справки: определение по формуле, является ли данная булева функция тождеством - это проблема P=?NP.

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

[Профессор Снэйп]

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

Можно ли по коду программы (булевой функции, алгоритма) определить ее свойства?

Смотря какие свойства.

Свойства программы по коду программы --- сплошь и рядом. Например, свойство "быть программой на бейсике" или "содержать более 300 строк". Короче, синтаксические свойства.

А вот свойства функции, которую программа вычисляет --- нет, не можете. На этот счёт есть теорема Райса.

[Xaositect]

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

Для справки: определение по формуле, является ли данная булева функция тождеством - это проблема P=?NP.

Точнее, эта задача coNP-полная.

[Ales]

Профессор Снэйп в сообщении #320042 писал(а):

вот свойства функции, которую программа вычисляет --- нет, не можете. На этот счёт есть теорема Райса.

Вопрос скорее по теории сложности, а не вычислимости.
Исследуемые программы должны быть ограничены по числу итераций, не допускается зависание,
не допускается самоприменение.
Обстоятельства приближены к реальной жизни.
А в реальной жизни нет возможности ждать долго,
программа работает час, не выдает ответ, все, опыт прекращается.

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

[Xaositect]

Тогда очерчивайте класс программ.

[Профессор Снэйп]

И класс свойств

[Ales]

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

Тогда очерчивайте класс программ.

Профессор Снэйп в сообщении #320092 писал(а):

И класс свойств

Пример:
Вопрос про биекции. Свойство - биекция.
Программа берет набор из 1000 нулей или единиц и вычисляет за 10000 шагов набор из 1000 нулей и единиц.
На каждом n-ом шаге, в зависимости от кода происходит: или $x_n=x_k \lor x_j$, или $x_n=x_k \& x_j$, или $x_n= \lnot x_k $, $k,j<n$.
$x_1,...,x_{1000}$ - входящие данные, $x_{9001},...,x_{10000}$ - исходящие данные.

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

[Профессор Снэйп]

Как-то не совсем понятно. Ресурсы алгоритма, распознающего свойства, тоже ограничены?

[Xaositect]

Это называется straight-line program и в булевом случае обычно переформулируется в терминах схем из функциональных элементов.

Итак, задача: Дана схема, реализующая некоторую функцию $\mathbb{B}^n\to\mathbb{B}^n$ ($\mathbb{B} = \{0,1\}$)
Определить, является ли эта функция биекцией.

Сведем к этой задаче уже упоминавшуюся задачу о тавтологии.
Пусть задана формула, построим по ней схему, у которой выход формулы просто размножен на $n$ выходов (это делается по формуле линейно) и прикрутим к выходам этой схемы дополнительно еще несколько операций так, чтобы $y'_i = \bar{y}_i \vee x_i$ ($x_i$ - i-й вход, $y_i$ - i-й выход, $y'_i$ - новый i-й выход). Для этого потребуется $2n$ новых элементов, так что это тоже линейно.
Эта схема реализует биекцию тогда и только тогда, когда исходная формула тавтологична на всем $\mathbb{B}^n$ без набора $(1, \dots, 1)$ (ну тут уж совсем техничская деталь доказать полиномиальнцю эквивалентность тавтологии и тавтологии без одного набора)

Т.о., поставленная задача coNP-трудна.

-- Вс май 16, 2010 16:43:52 --

Эта задача также лежит в coNP, т.к. ф-я $\mathbb{B}^n\to\mathbb{B}^n$ биекция тогда и только тогда. когда отображает различные точки в различные. Легко построить полиномиальную недетерминированную машину, которая останавливается на всех путях вычисления тогда и только тогда, когда выполняется это условие (выбираем недетерминированно два различных набора и вычисляем значения на них)

Значит, эта задача coNP-полна.

[Ales]

Профессор Снэйп в сообщении #320104 писал(а):

Как-то не совсем понятно. Ресурсы алгоритма, распознающего свойства, тоже ограничены?

Если по времени работы и по памяти - все ограничено.
Все надо делать на обычном персональном компьютере и на бейсике.
Больше нескольких минут работы - невозможно терпеть.

[Xaositect]

Я исправил свое сообщение, там были ошибки.

[Ales]

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

Сведем к этой задаче уже упоминавшуюся задачу о тавтологии.

Я попробую передать так как я понял. Пусть $f$ булева функция с короткой формулой: $x=(x_1,..,x_n), f: x \to \{ 0,1 \}$. Тогда отображение $(x_1,..,x_n) \to (x_1 \lor f(x) ,..,x_n \lor f(x)) $ биективно если и только если $f \equiv 0, x\ne (1,....,1)$.
В самом деле, если есть такое $x$, что $f(x)=1$, то его образ совпадет с образом неподвижного набора (1,...,1).

[Xaositect]

Да

-- Вс май 16, 2010 17:27:29 --

То есть, если мы умеем быстро определять биекции, то и тавтологии мы сможем определять быстро.

[Ales]

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

[Xaositect]

Да, много чего можем: можем любое свойство типа "для любых $k$ наборов $x_1,\dots,x_k$ выполняется $P(\pi; x_1, \dots x_k)$", где $\pi$ - это наша программа, а свойство $P$ вычисляется полиномиально.