2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Вопрос о принадлежности языка к классу P
Сообщение01.09.2020, 20:34 


16/12/14
474
Добрый вечер.

Допустим мы рассматриваем некоторый язык $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)}$?

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

 Профиль  
                  
 
 Re: Вопрос о принадлежности языка к классу P
Сообщение01.09.2020, 20:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос о принадлежности языка к классу P
Сообщение01.09.2020, 20:59 


16/12/14
474
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$

 Профиль  
                  
 
 Re: Вопрос о принадлежности языка к классу P
Сообщение01.09.2020, 21:03 
Заслуженный участник
Аватара пользователя


16/07/14
9534
Цюрих
Pulseofmalstrem в сообщении #1481598 писал(а):
Берем, функцию с картой Карно, в которой разбросанны единицы в шахматном порядке
А как строки и столбцы упорядочены? Если лексикографически, то там всего две существенных переменных получится.

 Профиль  
                  
 
 Re: Вопрос о принадлежности языка к классу P
Сообщение01.09.2020, 21:07 


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

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

 Профиль  
                  
 
 Re: Вопрос о принадлежности языка к классу P
Сообщение01.09.2020, 21:14 
Заслуженный участник
Аватара пользователя


16/07/14
9534
Цюрих
Pulseofmalstrem в сообщении #1481602 писал(а):
Строки и столбцы упорядочены по рефлексивному коду Грея
Тогда функция существенно зависит только от четырех переменных, и соответственно у неё опять же есть короткие ДНФ и КНФ.
Pulseofmalstrem в сообщении #1481602 писал(а):
Просто я пытался её построить заведомо так, чтобы быстро вычислить было нельзя.
Ну вы же по сути её заданием описали быстрый алгоритм вычисления - можно по набору переменных быстро найти номера строки и столбца, и узнать значение функции.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: oleg_2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group