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

[Ales]

Обратно тоже можно реализовать: $(g(x)\ne g(y)) \lor (x=y) \equiv 1 \Longleftrightarrow g: x \to y$ - биекция.

-- Вс май 16, 2010 18:03:38 --

Итак, с биекцией разобрались - это та же проверка на тавтологию.

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

Такие отображения тоже годятся как шифрователи.

-- Вс май 16, 2010 18:09:30 --

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

[Xaositect]

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

Итак, с биекцией разобрались - это та же проверка на тавтологию.

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

Такие отображения тоже годятся как шифрователи.

Давайте поставим задачу так: задан некоторый положительный полином $p(n)$. Необходимо по заданной схеме $\Sigma$, задающей оператор $f\colon\mathbb{B}^n\to\mathbb{B}^n$, выяснить, верно ли, что прообраз любого эл-та $\mathbb{B}^n$ содержит не более $p(n)$ наборов.

И будем думать.

-- Вс май 16, 2010 21:47:47 --

В общем, можно действовать похожим образом.

Пусть есть формула $\Phi$, задающая функцию $\varphi\colon \mathbb{B}^m\to \mathbb{B}$. Построим по ней оператор $f\colon\mathbb{B}^n\to\mathbb{B}^n$, где $n - k\log n= m$, следующим образом: если $\phi(\sigma_1,\dots,\sigma_m) = 1$, то $f(\sigma_1,\dots,\sigma_m,\alpha_{m+1},\dots,\alpha_{n}) = (\sigma_1,\dots,\sigma_m,0,\dots,0)$ для любых $\alpha_i$. если же $\varphi(\sigma_1,\dots,\sigma_m) = 0$, то $f(\sigma_1,\dots,\sigma_m,\alpha_{m+1},\dots,\alpha_{n}) = (0,\dots,0)$. Понятно, что схему $\Sigma$ для такого оператора можно достаточно быстро (полиномиально) построить по формуле $\Phi$.
Теперь, если $\varphi(x_1,\dots,x_m) = 1$ для всех $x$, кроме, может быть, $(0,\dots,0)$, то каждый набор имеет не более $2^{n-m} = n^k$ прообразов. А если где-то функция равна 0, то набор $(0,\dots,0)$ имеет как минимум $2\cdot 2^{n-m} = 2n^k$ прообразов.

То есть, если мы можем быстро определять, все ли прообразы имеют мощность не более $n^k$, то мы можем быстро определять тавтологичность формул с $n-k\log n$ переменными.

Тут, по-хорошему, надо побольше расписать технические детали, целые части правильно расставить, сказать, что это для достаточно больших $n$, но идея такая.

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

[Ales]

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

В общем, можно действовать похожим образом.

Получается, что Вы доказали соNP-полность задачи о точной оценке числа образов для функции.
Биекция - частный случай, с числом образов 1. Здорово.

Остается вопрос о почти точных (вероятностных) оценках. Здесь совсем по другому.

[Ales]

То есть, числа прообразов. Образов для обратной функции.

[Ales]

Можно ли любое разумное универсальное свойство для функции $f: \mathbb B^m \to \mathbb B^k$ формализовать,
как $p(f(x_1),f(x_2),....,f(x_n),x_1,.....,x_n) \equiv 1$, $p: \mathbb B^{(m+k)n} \to \mathbb B$?
Кажется можно, но лень доказывать, не известный ли это факт?

Тогда может быть получится распространить доказательства Xaositect на общий случай любого свойства?

-- Пн май 17, 2010 22:34:14 --

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

[Xaositect]

Ну если $p$ произвольное и $n$ зависит от арности функции, то да.
Если брать $p$ быстро вычислимым, а $n$ полиномиальным, то нет. (Все задачи такого вида лежат в coNP).
Вот, скажем, выполнимость ($\exists x (f(x) = 1)$)- NP-полная задача. Если бы она лежала в coNP, то NP=coNP. Это не доказано, и специалисты считают, что скорее всего неверно.

-- Пн май 17, 2010 22:38:18 --

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

[Ales]

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

Ну если $p$ произвольное и $n$ зависит от арности функции, то да.
Если брать $p$ быстро вычислимым, а $n$ полиномиальным, то нет. (Все задачи такого вида лежат в coNP).
Вот, скажем, выполнимость ($\exists x (f(x) = 1)$)- NP-полная задача. Если бы она лежала в coNP, то NP=coNP. Это не доказано, и специалисты считают, что скорее всего неверно.

-- Пн май 17, 2010 22:38:18 --

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

Что-то я плохо это понял. Я ведь недозагружен теорией.
И не помню что такое "coNP". Но это я найду в интернете.

Что такое "арность", и к чему относятся "да", "нет"?

Разве ($\exists x (f(x) = 1)$) не то же самое, что проверить на тавтологию?

-- Пн май 17, 2010 23:10:12 --

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

[Xaositect]

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

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

Ну если $p$ произвольное и $n$ зависит от арности функции, то да.
Если брать $p$ быстро вычислимым, а $n$ полиномиальным, то нет. (Все задачи такого вида лежат в coNP).
Вот, скажем, выполнимость ($\exists x (f(x) = 1)$)- NP-полная задача. Если бы она лежала в coNP, то NP=coNP. Это не доказано, и специалисты считают, что скорее всего неверно.

-- Пн май 17, 2010 22:38:18 --

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

Что-то я плохо это понял. Я ведь недозагружен теорией.
И не помню что такое "coNP". Но это я найду в интернете.

Что такое "арность", и к чему относятся "да", "нет"?

Разве ($\exists x (f(x) = 1)$) не то же самое, что проверить на тавтологию?

Арность, местность - количество аргументов функции.

Тавтология - это $\forall x (f(x) = 1)$, а $\exists x (f(x) = 1)$ - это выполнимость.

"Да" и "нет" относится к следующему - любое свойство булевой функции $f\colon\mathbb{B}^k \to\mathbb{B}$ можно представить в виде $(\forall x_i) p(x_1,\dots,x_n,f(x_1),\dots,f(x_n)) = 1$, но $n$ здесь может быть очень большим, а $p$ - очень сложной. Например, $\exists x (f(x) = 1) \equiv \bigvee\limits_{x_i\in \mathbb{B}^k} f(x_i)$, т.е. здесь $n = 2^k$ и не очень понятно, можно ли его уменьшить.

Если поставить условие, что $n = \mathrm{poly}(k)$ (не больше некоторого полинома), а функция $p$ вычисляется полиномиальным алгоритмом, то в виде

$$\begin{equation}(\forall x_i) p(x_1,\dots,x_n,f(x_1),\dots,f(x_n)) = 1\end{equation}$$

представляются только coNP-свойства.

Ну и про NP и coNP я все-таки напишу. NP - это класс свойств, для которых существует сертификат принадлежжности, то есть мы можем быстро проверить, удовлетворяет ли объект NP-свойству, если задана некоторая доп. информация. А coNP - это те, для которых существует сертификат отвергающий, т.е. можно быстро проверить, что функция классу не принадлежит. Разумеется, если задача проверки некоторого свойства S лежит в NP, то задача проверки того, что объект не обладает этим свойством, лежит в coNP.

Например, в случае тавтологии можно легко проверить, что функция не тавтология, если задан набор, где она равна 0. А в случае выполнимости можно легко проверить, что функция выполнима, если задан набор, где она 1. Значит, тавтология - задача из coNP, а выполнимость - NP. Считается более правдоподобным, что NP не равно coNP, поэтому NP-полные свойства вряд ли можно представить в виде (1)

В принципе, можно проверить и более сложные свойства, которые, скорее всего, не будут лежать ни в NP, ни в coNP.

[Ales]

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

Тавтология - это $\forall x (f(x) = 1)$, а $\exists x (f(x) = 1)$ - это выполнимость.

Я имел в виду проверку $\forall x (f(x) = 0)$ или то же самое $ \lnot f(x) \equiv 1$, разве это не эквивалентно проверке $\exists x (f(x) = 1)$. Если есть быстрый алгоритм проверяющий первое (да или нет), то он же дает ответ на второе и наоборот.
Или не так? Что я понимаю не верно?

[Xaositect]

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

Или не так? Что я понимаю не верно?

Все так. Но сейчас считается более правдоподобным вариант, что такого быстрого алгоритма не существует.

[Ales]

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

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

Или не так? Что я понимаю не верно?

Все так. Но сейчас считается более правдоподобным вариант, что такого быстрого алгоритма не существует.

Я запутался: проверка на тавтологию coNP, проверка существования решения NP.
Это одно и тоже, но почему то разное.

[Xaositect]

Я, наверное, несколько сумбурно написал. Мб завтра напишу подробнее.

Это все было по поводу Вашего вопроса о представлении свойств в определенном виде. Вот строгий ответ на него: если NP не равно coNP, то не любое свойство булевой функции $f\colon\mathbb{B}^k\to\mathbb{B}$ может быть представлено в виде $p(x_1,\dots,x_n,f(x_1),\dots,f(x_n)) = 1$, где $n = k^{O(1)}$, а $p$ вычисляется полиномиальным алгоритмом по формуле для функции $f$ и наборам $x_i$.

-- Пн май 17, 2010 23:29:14 --

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

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

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

Или не так? Что я понимаю не верно?

Все так. Но сейчас считается более правдоподобным вариант, что такого быстрого алгоритма не существует.

Я запутался: проверка на тавтологию coNP, проверка существования решения NP.
Это одно и тоже, но почему то разное.

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

[Ales]

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

любое свойство булевой функции можно представить в виде

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

-- Пн май 17, 2010 23:40:15 --

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

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

А если решения нет, то что? Какую подсказку дают?

[Xaositect]

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

Для таких разве тоже нужна очень сложная функция?

Ну можно придумать достаточно простые свойства, которые, скорее всего, ни в NP, ни в coNP не лежат.
Вот например, дана функция от $2k$ переменных. Проверить, что для любых $y_i$ найдется такие $z_i$, что $f(y_1,\dots,y_k,z_1,\dots,z_k) = 1$.
Если писать это свойство в виде $p(x_1,\dots,x_n,f(x_1),\dots,f(x_n)) = 1$, то получится $n = 2^k$ и свойство $p$ будет выглядеть как "если все $x_i$ начинаются с одинаковых $k$ бит, то дизъюнкция $\bigvee\limits_{i = 1}^{n} f(x_i) = 1$"

-- Пн май 17, 2010 23:50:48 --

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

А если решения нет, то что? Какую подсказку дают?

Подсказка - это собственно набор, на котором функция равна 1.
А вот если решения нет, то и подсказки нет.

[Ales]

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

А вот если решения нет, то и подсказки нет.

А разве тогда из факта отсутствия подсказки нельзя вывести, что решения нет?
Или это будет не по правилам?