Вопрос о принадлежности языка к классу P

[Pulseofmalstrem]

Добрый вечер.

Допустим мы рассматриваем некоторый язык $L$ слова которого записываются в обычном двоичном алфавите $\Sigma = {0,1}$. В таком случае язык порождает семейство булевых функций $f_n (x_1, \dots, x_n)$ по правилу:

$f(x_1, \dots, x_n) = 1$, если слово $x_1 \dots x_n$ принадлежит языку $L$, и $f(x_1, \dots, x_n) = 0$ в противном случае.

Вопрос: можно ли считать, что язык $L$ не решается (не определеяется) за полиномиальное время, если известно, что длина минимальной дизьюктивной и коньюктивной нормальной формы, задающей семейство $f_n$ (под длиной имеется ввиду число операций в форме) растет как $2^{(n-1)}$?

Вроде бы ответ да можно, так как булевого узла короткого не найдется, но так ли это?

[mihaild]

А вы знаете какие-нибудь просто вычислимые функции с длинной КНФ или ДНФ? Например функцию с короткой КНФ, но длинной ДНФ (или наоборот)?

[Pulseofmalstrem]

mihaild
Берем, функцию с картой Карно, в которой разбросаны единицы в шахматном порядке. Нет сверток ни для ДНФ ни для КНФ, поэтому остаются вроде бы остаются только СДНФ и СКНФ по обоих случаях длиной в $2^{(n-1)}}$ блока.

Ну, например, при $n=3$ таблица Карно такой интересной функции запишется:

$$\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1\\ \end{pmatrix}$$

И соответственно СДНФ будет вот такой:
$f = \overline{x}_1 \overline{x}_2 \overline{x}_3 \vee x_1 \overline{x}_2 x_3 \vee \overline{x}_1 x_2 x_3 \vee x_1 x_2 \overline{x}_3$

[mihaild]

Pulseofmalstrem в сообщении #1481598 писал(а):

Берем, функцию с картой Карно, в которой разбросанны единицы в шахматном порядке

А как строки и столбцы упорядочены? Если лексикографически, то там всего две существенных переменных получится.

[Pulseofmalstrem]

mihaild
Строки и столбцы упорядочены по рефлексивному коду Грея.

Мне интересно вычисляется ли такая функция быстро или нет. Просто я пытался её построить заведомо так, чтобы быстро вычислить было нельзя. Вопрос преуспел ли я в этом.

[mihaild]

Pulseofmalstrem в сообщении #1481602 писал(а):

Строки и столбцы упорядочены по рефлексивному коду Грея

Тогда функция существенно зависит только от четырех переменных, и соответственно у неё опять же есть короткие ДНФ и КНФ.

Pulseofmalstrem в сообщении #1481602 писал(а):

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

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