Main problems of linear algebra related with SATISFIABILITY problem.pdf Рассмотрим переход от задачи 3-ВЫПОЛНИМОСТЬ к задаче решения систем линейныхалгебраических уравнений. Пусть дана КНФ:MЦ х) = П C , (1)i=1где C - дизъюнкты вида Vqjj . Здесь qjj = х^ или qjj = х^ .Заметим, что каждому дизъюнкту можно поставить в соответствие уравнение, связывающееуже вещественные переменные. В правой части стоят единицы, а переходот булевых переменных к вещественным осуществляется согласно формулам: х^ ^ y j,х^ ^ 1 - yj . В этом случае мы получаем систему линейных алгебраических уравненийс прямоугольной матрицей:Ay = f. (2)Обратим внимание на то очевидное обстоятельство, что правая часть f равна количествуqjj , принимающих значение ИСТИНА в исходной КНФ. Систему можно преобразоватьсогласно формулеRAy = B f = R f = g. (3)Попытаемся построить матрицу B таким образом, чтобы получить в итоге симметричнуюматрицу. Рассмотрим переменную с индексом j и соответствующие ей уравненияв (3). Будем складывать эти уравнения, аккумулируя неизвестные в j -й строке B ,умножая их на -1 , если переменная входит в уравнение со знаком минус. Тогда вернаследующая лемма.Лемма. Итоговая матрица B симметрична.Рассмотрим общий случай, не предполагающий специальной структуры матрицы.Воспользуемся тем, что матрица симметрична и спектр ее вещественный, тогда можнозаписать NУ = X aiVi,i=1где Vi - это собственные векторы, отвечающие собственным числам, определяемым изуравненияBvi = AiVi. (4)Здесь Ai могут быть равны нулю. Правая часть системы (3) представляется в видеNg = X Ai«iVi.i=1В итоге верна следующая теорема.Теорема. Компоненты кортежей (a 1, .., « n), на которых достигается равный нулюминимум функционалаM 3J (ai, ...,aN) = ЕП Cq + I (a i ,..., «n ),j=i q=iC = (q - . )2,Sq = (г1,г2,гз,Т1,Т2,гз), т = 1 V 0, it e {1 ,...,N },3e.q = . ( - i ) T' (yi. - т.).s=1Naw VWw=1N.■1 (a i , ..., aN) = X У2(1 - yz)2,z=1являются коэффициентами разложения решения задачи ВЫПОЛНИМОСТЬ у == ^2N=1 aivi, где индекс w при v индексирует номер собственного вектора, множествоиндексов Sq - это номера литералов, входящих в j -й дизъюнкт, и отвечающиеим индексы т , определяющие, как входит литерал в дизъюнкт, с отрицанием или безнего.Данные результаты позволяют для некоторых классов задач определять четвертьчасти решающего набора для 3-SAT с вероятностью, равной или больше 0,9.

Скачать электронную версию публикации