Научная Сеть >> М.Н. Вялый "Сложность вычислительных задач"

Наука >> Математика >> Математическое образование | Популярные статьи

Next: 2. Способы решения задач Up: Сложность вычислительных задач Previous: Содержание Contents: Содержание

1. Вычисление каких функций рассматривается

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

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

Пока мы говорили о функциях от одного аргумента. В дальнейшем будут возникать и функции от нескольких аргументов. Увеличение алфавита на 1 символ (обозначим его $\char93$ ) позволяет закодировать конечную последовательность слов $\alpha_1,\dots,\alpha_n$ в алфавите одним словом

$\begin{displaymath} \alpha_1\char93 \alpha_2\char93 \dots\char93 \alpha_n\char93 \end{displaymath}$ (1)

в алфавите $A\cup \{\char93 \}$ . Будем иметь в виду это преобразование в тех случаях, когда возникает желание рассматривать функцию от нескольких аргументов как функцию от одного аргумента.

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

Пример 1. Линейные уравнения над $\QQ$ .

Даны: матрица размера $m\times n$ , элементы которой - рациональные числа, вектор-столбец (матрица размера $m\times1$ ), также состоящий из рациональных чисел.

Спрашивается: разрешима ли в рациональных числах система

$\begin{displaymath} Ax=b? \end{displaymath}$ (2)

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

$\begin{displaymath} \{0,1,\char93 , /, -\}. \end{displaymath}$

Целые числа будем записывать в двоичной системе, используя знак "

" для обозначения отрицательных чисел. Рациональное число

будем записывать словом $\mathop{код}\nolimits (p) / \mathop{код}\nolimits (q)$ , а последовательность чисел будем записывать, разделяя записи различных чисел знаком $\char93$ .

В описанной кодировке вход задачи линейные уравнения над $\QQ$ - слово $\mathop{код}\nolimits (Ax=b)$ , кодирующее последовательность чисел

$\begin{displaymath} m, n, a_{11},\dots,a_{1n}, a_{21},\dots,a_{2n}, \dots, a_{m1},\dots,a_{mn}, b_{1},\dots,b_{m}, \end{displaymath}$

где $a_{ij}$ - элементы матрицы

- элементы

Функция, которую нужно вычислить, имеет вид

$\begin{displaymath} \chi(t)=\left\{\begin{aligned} 1&, \text{ если $t=\mathop{ко... ... не определено в любом другом случае}.\\ \end{aligned}\right. \end{displaymath}$ (3)

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

Сформулируем еще несколько задач о разрешимости уравнений в виде задач вычисления характеристической функции некоторого предиката. Во всех упомянутых ниже задачах о разрешимости уравнений или систем уравнений подразумевается, что вычисляется характеристическая функция, аналогичная (3).

Пример 2. Линейные уравнения над $\ZZ^{+}$ .

Даны: матрица размера $m\times n$ , элементы которой - целые числа, вектор-столбец (матрица размера $m\times1$ ), также состоящий из целых чисел.

Спрашивается: разрешима ли в неотрицательных целых числах система уравнений

$\begin{displaymath} Ax=b? \end{displaymath}$ (4)

Пример 3. Система уравнений в $\FF_2$ .

Даны: многочлены $p_1,\dots, p_k\in\FF_2[x_1,\dots,x_n]$ .

Спрашивается: разрешима ли в поле $\FF_2$ система уравнений

$\begin{displaymath} p_i(x_1,\dots,x_n)=0,\quad i=1,\dots,k? \end{displaymath}$ (5)

Как кодировать многочлен словом в некотором алфавите? Можно, например, указать степень многочлена и количество переменных , представить многочлен в виде суммы мономов

$\begin{displaymath} p(x_1,\dots,x_n)=\sum_{\alpha_1+\ldots+\alpha_n\leq d}^{} p_... ...ts\alpha_n}x_1^{\alpha_1} x_2^{\alpha_2}\ldots x_n^{\alpha_n}, \end{displaymath}$

после чего перечислить коэффициенты его мономов в некотором оговоренном заранее порядке. Другой способ состоит в том, чтобы перечислить все ненулевые мономы, указывая также их коэффициенты. Эти способы могут приводить к записям весьма разной длины: длина записи многочлена $x_1\cdot\ldots\cdot x_n$ первым способом порядка

, а вторым - не больше, чем $n\log n$ .

Пример 4. Уравнение над $\ZZ$ .

Дан: многочлен $p\in\ZZ[x_1,\dots,x_n]$ .

Спрашивается: есть ли решения в целых числах у уравнения

$\begin{displaymath} p(x_1,\dots,x_n)=0? \end{displaymath}$ (6)

Next: 2. Способы решения задач Up: Сложность вычислительных задач Previous: Содержание Contents: Содержание

МЦНМО

Написать комментарий