Содержание к диссертации
Введение
Глава 1. Свойства пороговых и близких к ним функций 32
1.1. Определения исследуемых классов функций 32
1.2. Величина коэффициентов характеристической системы . 35
1.3. Число вершин в P0(f) и P1(f) 38
1.4. Мощностные свойства исследуемых классов функций . 44
1.5. Соотношение между классами T(M) и F0(M) F1(M) . 47
1.6. Построение двойственного описания полиэдра 53
1.6.1. Введение 54
1.6.2. Определения и предварительные сведения . 58
1.6.3. Метод двойного описания 60
1.6.4. Порядок добавления неравенств 62
1.6.5. Методы проверки смежности экстремальных лучей 64
1.6.6. Уменьшение количества рассматриваемых пар смежных лучей 68
1.6.7. Вычислительный эксперимент 69
Глава 2. Алгоритмы расшифровки пороговых и близких к ним функций 74
2.1. Постановка задачи 74
2.2. Безусловные тесты для пороговых функций 78
2.3. Расшифровка функций в классе F0(M) F1(M) 79
2.3.1. Оракульный алгоритм максимизация линейной функции 80
2.3.2. Алгоритм расшифровки в классе F0(M) F1(M) . 83
2.4. Расшифровка пороговых функций 87
2.4.1. Расшифровка функций из класса T+(M) 88
2.4.2. Расшифровка функций из класса T(M) 95
2.4.3. Модификация алгоритма 97
2.5. Расшифровка пороговых функций двух переменных . 99
2.6. Расшифровка пороговых функций, заданных расширенным оракулом 107
Глава 3. Нижние оценки сложности расшифровки 113
3.1. Введение 113
3.2. Свойства конуса разделяющих функционалов 117
3.3. Структура разрешающего множества пороговой функции 120
3.4. Оценки длины обучения в классе пороговых функций . 125
3.5. Другая характеризация минимального разрешающего множества пороговой функции 131
3.6. Верхняя оценка мощности минимального разрешающего множества для одного подкласса пороговых функций . 136
3.7. Неприводимые целочисленные точки политопов 140
3.7.1. Неприводимые точки в параллелепипеде 141
3.7.2. Покрытие политопа параллелепипедами 144
3.7.3. Неприводимые точки в политопе 148
3.8. Верхние оценки длины обучения в классе пороговых функций 150
3.9. Построение минимального разрешающего множества пороговой функции 153
3.10. Минимальное разрешающее множество пороговой функции двух переменных 156
3.10.1. Мощность разрешающего множества 157
3.10.2. Среднее значение мощности минимального разрешающего множества пороговой функции
двух переменных 162
3.10.3. Свойства специальных разбиений плоскости
прямыми 167
3.11. Сложность расшифровки пороговых булевых функций 170
3.12. Оракульная сложность задачи о рюкзаке 171
Глава 4. Расшифровка пороговых функций и диофантовы приближения 174
4.1. Диофантовы приближения вещественных чисел 174
4.2. Связь задачи расшифровки с задачей приближения . 177
4.3. Диофантовы приближения алгебраических чисел 182
Заключение 184
Литература
- Мощностные свойства исследуемых классов функций
- Расшифровка функций в классе F0(M) F1(M)
- Оценки длины обучения в классе пороговых функций
- Связь задачи расшифровки с задачей приближения
Введение к работе
Актуальность темы исследований. В целом ряде разделов математической кибернетики возникает задача восстановления (расшифровки) неизвестной дискретной функции из заданного класса с помощью последовательных вопросов о ее значении в точке. Требуется отыскать алгоритм расшифровки, использующий по возможности минимальное число вопросов о значении функции и приемлемое время для промежуточных вычислений.
Наиболее известной проблемой из этой серии является впервые рассмотренная В. К. Коробковым и Т. Л. Резником задача расшифровки монотонных булевых и многозначных функций [26, 27]. Известна сводимость к последней проблеме целого класса задач математической логики, математической экономики, целочисленного линейного программирования, теории распознавания образов.
В.Н.Шевченко рассмотрел задачу расшифровки пороговых функций А-знач-ной логики [37-39]. Пороговые функции возникают во многих разделах математической кибернетики и дискретной математики и приложениях, например, в дискретной оптимизации [33, 39], распознавании образов [20, 21, 48], теории графов [19], при синтезе схем из функциональных элементов [29, 30, 32], нейронных сетей [42], в цифровой обработке сигналов [18, 50]. Их можно интерпретировать как характеристические функции подмножеств множества {0,1,... ,к — 1}л, обладающих специальным свойством «линейной отделимости». В связи с последней возможностью естественно стремление расширить их область определения. Значительный интерес имеют постановки задач, в которых функции определены на множестве М целочисленных решений заданной системы линейных неравенств. Функция, отображающая М в множество {0,1}, называется пороговой, если найдется гиперплоскость, разделяющая множества ее нулей и единиц (точек, в которых функция равна нулю или единице соответственно). К расшифровке таких функций сводятся специальные задачи теории распознавания образов с линейной разделяющей поверхностью. Большое значение задача расшифровки пороговых функций имеет в машинном обучении [48]. Другой смежной областью является связанная с большим кругом приложений теория тестов [28, 31, 34]. Таким образом, до-
статочно важным является целый ряд проблем, связанных с пороговыми функциями и их расшифровкой. Как правило, возникающие задачи — весьма сложные. Широко известной трудной проблемой, например, является оценка числа пороговых булевых функций. Для этой величины известна лишь установленная Ю.А.Зуевым [23] асимптотика ее логарифма. Асимптотика логарифма числа пороговых функций А-значной логики установлена А. А. Ирматовым и Ж. Д. Ковиянич [25]. Обстоятельный обзор результатов по пороговым булевым функциям и пороговым представлениям булевых функций содержится в [24].
Естественной мерой сложности алгоритма расшифровки является минимальное число вопросов, достаточное для расшифровки любой функции из заданного класса (оракулъная сложность). Другой характеристикой является вычислительная трудоемкость — число операций, выполненных алгоритмом в худшем случае.
В.Н.Шевченко [38] предложил алгоритм расшифровки пороговой функции А-значной логики, имеющий при любом фиксированном п полиномиальные от log к оракульную сложность и вычислительную трудоемкость. Верхнюю оценку сложности алгоритма В.Н.Шевченко уточнил Т.Hegedtis [46], см. также [47]. В.Н.Шевченко [38] также показал, что полиномиального от п алгоритма, решающего данную задачу, не существует. Таким образом, для задачи расшифровки пороговой функции приведенные результаты заставляют ограничиться поиском алгоритмов, полиномиальных при фиксированном п. Для оценки их качества и для характеризации сложности всей задачи расшифровки пороговых функций необходимы результаты о близости предлагаемых алгоритмов к оптимальным. В частности, представляет интерес поиск нижних оценок сложности расшифровки, что приводит к исследованию структурных и мощностных свойств так называемого разрешающего множества [26] пороговой функции — такого множества точек из области определения М, значений функции в которых достаточно для однозначного восстановления функции в остальных точках. Дальнейшие результаты в этих направлениях означали бы более глубокое исследование структурных свойств и, возможно, мощностных характеристик класса пороговых функций.
До исследований автора нетривиальных нижний оценок сложности расшифровки пороговых функций (при фиксированном п и к —> ) известно не
было. М. Anthony, G. Brightwell, J. Shawe-Taylor [43] получили верхнюю оценку средней мощности минимального разрешающего множества пороговой функции. W. J. Bultman и W. Maass [44] исследовали сложность расшифровки пороговой функции, зависящей от двух переменных (использовалась несколько отличная терминология).
Цель работы заключается в построении эффективных алгоритмов расшифровки пороговых и близких к ним функций, определенных на множестве целочисленных решений заданной системы линейных неравенств; установлении нижних оценок сложности задачи расшифровки; анализе структурных и мощностных свойств минимального разрешающего множества пороговой функции. Особое внимание уделяется пороговым функциям А-значной логики, зависящих от п переменных.
Методы исследований. При построении алгоритмов расшифровки использовались результаты и методы целочисленного линейного программирования, теории систем линейных неравенств, теории чисел, комбинаторики. Некоторые алгоритмы используют и развивают подходы, предложенные В. Н. Шевченко при разработке им алгоритма расшифровки пороговых функций А-значной логики. При построении верхних и нижний оценок сложности расшифровки успешно применяются результаты о числе вершин выпуклой оболочки целочисленных решений систем линейных неравенств, полученные В.Н.Шевченко и его учениками [39]. Данный подход был применен и усовершенствован диссертантом для получения верхней оценки числа неприводимых точек политопа, что использовалось при построении неулучшаемой (по порядку при фиксированном п) верхней оценки мощности минимального разрешающего множества пороговой функции. Предложен новый подход, на основе которого получена нетривиальная нижняя оценка сложности расшифровки пороговой функции А-значной логики.
Научная новизна. Диссертация посвящена изучению задачи расшифровки пороговых и близких к ним функций, заданных на множестве целочисленных решений системы линейных неравенств (целых точек политопа). Особое внимание уделяется важному частному случаю — пороговым функциям А-значной логики. Все полученные результаты являются новыми и могут быть
кратко сформулированы следующим образом:
-
Разработан алгоритм расшифровки функций, заданных на множестве целочисленных точек политопа и обладающих свойством, что множества нулей и единиц каждой такой функции можно описать системами линейных неравенств. При любой фиксированной размерности п и некоторых дополнительных ограничениях алгоритм является полиномиальным от размера линейной системы, описывающей политоп.
-
Для пороговых функций, определенных на множестве целочисленных точек политопа, предложен алгоритм расшифровки, при фиксированной размерности полиномиальный от размера задания политопа. Установлена нижняя оценка сложности этой задачи. Оракульная сложность предложенного алгоритма при фиксированном п близка по порядку к нижней оценке сложности.
-
Для пороговых функций А-значной логики предложен алгоритм расшифровки, полиномиальный при фиксированном п. Установлена нижняя оценка сложности этой задачи. Оракульная сложность предложенного алгоритма при фиксированном п близка по порядку к нижней оценке сложности.
-
Описано строение минимального разрешающего множества пороговой функции А-значной логики. Найдены верхняя и нижняя оценка длины обучения в классе таких функций; при фиксированном п эти оценки совпадают по порядку.
-
Разработан алгоритм расшифровки пороговых функций А-значной логики, зависящих от двух переменных. Для этих функций установлен порядок сложности расшифровки, найдены точное значение длины обучения и асимптотическое значение средней мощности минимального разрешающего множества.
-
Установлена связь задачи расшифровки пороговой функции двух переменных с проблемой нахождения диофантовых приближений вещественных чисел. Предложен полиномиальный алгоритм приближения веще-
ственного числа, заданного оракулом, и полиномиальный алгоритм приближения алгебраического числа, заданного минимальным многочленом.
7) Предлагается новая модификация («графовый» тест проверки смежности экстремальных лучей) метода двойного описания построения вершинного описания полиэдра. Теоретическая оценка сложности построенной модификации и результаты экспериментов показали преимущество алгоритма по сравнению с классическим его вариантом.
Теоретическая и практическая значимость. Работа носит теоретический характер. Полученные в диссертации результаты могут быть использованы при дальнейших исследованиях пороговых функций, в частности, при изучении их структуры, числа, соотношения с другими близкими функциями и т. п. Диссертация имеет ценность для таких приложений, как дискретная оптимизация, распознавание образов, машинное обучение. Новая модификация метода двойного описания может использоваться в практических приложениях, где встречается задача построения общего решения системы линейных неравенств и двойственная к ней задача, например, в оптимизации, вычислительной физике, биоинформатике и др.
Результаты диссертации могут найти применение в исследованиях, проводимых в Московском государственном университете им. М. В. Ломоносова, Вычислительном центре им. А. А. Дородницына РАН, Институте прикладной математики им. М. В. Келдыша РАН, Институте математики им. С. Л. Соболева Сибирского отделения РАН, Нижегородском государственном университете им. Н. И. Лобачевского.
Апробация работы. Результаты диссертации докладывались и обсуждались на Международных семинарах «Дискретная математика и ее приложения» (Москва, 1995, 1998, 2001, 2004, 2007, 2012), на XVI Международной конференции «Проблемы теоретической кибернетики» (Нижний Новгород, 2011), на Международных конференциях «Математические алгоритмы» (Нижний Новгород, 1994, 1995), на Международной конференции «Алгебра и линейная оптимизация», посвященной 100-летию С.Н.Черникова (Екатеринбург, 2012) на Всероссийской конференции «Проблемы оптимизации и эко-
номические приложения» (Омск, 2006), на Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2007, 2011), на Российских конференциях «Дискретный анализ и исследование операций» (Новосибирск, 2004), «Дискретная оптимизация и исследование операций» (Алтай, 2010), на школе-семинаре «Синтез и сложность управляющих систем» (Нижний Новгород, 1994; Нижний Новгород, 2000; Пенза, 2002; Нижний Новгород, 2003), на Молодежной научной школе по дискретной математике и ее приложениям под руководством чл.-корр. РАН О. Б. Лупанова (Москва, 1997; Москва, 2000; Нижний Новгород, 2001), на заседаниях спецсеминара «Дискретная математика и математическая кибернетика» ВМК МГУ, Нижегородского семинара по дискретной математики.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Общий объем работы — 208 страниц. Список литературы содержит 167 наименований. В первой главе содержатся результаты о пороговых и близких к ним функциях, которые далее используются для построения алгоритмов расшифровки и установлении нижних оценок сложности. Во второй главе предлагаются алгоритмы расшифровки пороговых и близких к ним функций. Третья глава посвящена нижним оценкам сложности задачи расшифровки. В ней также описаны результаты о структурных и мощностных свойствах разрешающего множества пороговой функции. В четвертой главе устанавливается связь между задачей расшифровки пороговой функцией и задачей нахождения наилучшего диофантового приближения.
Мощностные свойства исследуемых классов функций
В разделе 3.7 получены верхние оценки количества неприводимых точек в полиэдре (далее, в разделе 3.8, эти оценки используются для получения верхней оценки o (Ef) = 0(\ogn 2 к) при фиксированном п 2). Пусть Р — полиэдр в R". Точка iG Р Є Z" называется неприводимой в Р (а, точнее, в РП Z"), если х нельзя представить в виде х = (у + z) ни для каких двух различных у и z из РП Z73. Пусть Р, P\,P2,...,PS {Рь Р2 , Ps} называется покрытием политопа Р. Если пересечение любых двух политопов в покрытии либо пусто, либо является их общей гранью, то покрытие называется правильным разбиением. Если все политопы в правильном разбиении — симплексы, то разбиение называется триангуляцией. Основная идея получения верхней оценки числа неприводимых точек в политопе заключается в следующем. В подразделе 3.7.1 получена оценка количества неприводимых точек в параллелепипеде. В подразделе 3.7.2 показано, как для произвольного политопа Рпостроить его покрытие параллелепипедами Р\, Pi,..., Ps. Для этого сначала строится триангуляция политопа, а затем каждый симплекс триангуляции покрывается параллелепипедами. Легко видеть, что любая неприводимая в РП Ъп точка х неприводима и в Р2- П Ъп для любого і, если х є Р[. Это свойство позволяет в подразделе 3.7.3 оценить количество неприводимых точек в Р. А именно, доказано, что если Р можно задать системой т линейных неравенств и Р П Z" С Епк, то количество неприводимых в PP\Zn точек есть 0(#?LfJ log73-1 к). Заметим, что полученная оценка представляет самостоятельный интерес. В разделе 3.8 она используется для получения неулучшаемой верхней оценки длины обучения в классе пороговых функций.
В разделе 3.9 изучается задача построения минимального разрешающего множества пороговой функции f є %{М), М = Р П Ъп, по известным коэффициентам порогового неравенства и по известной системе, описывающей политоп Р. Для решения этой задача предлагается полиномиальная от logy и І процедура (п фиксировано). Показано, как изменить алгоритм &/\, чтобы сложность нового алгоритма &/ отличалась бы от сложности оптимального (по числу обращений к оракулу в худшем случае) алгоритма расшифровки не более, чем в 0(r? \og(ny)) раз. Для класса X(Ef) сложность алгоритма &/ отличается от сложности оптимального алгоритма не более, чем в О [г? \og(nkj) раз и при фиксированном п
В разделе 3.10 рассматривается случай пороговых функций двух переменных. Из результатов предыдущих разделов вытекает 41ogA r( ) 61ogA. Для длины обучения в классе (іф в подразделе 3.10.1 установлено точное значение cr(El) = 4. В подразделе 3.10.2 получена асимптотика среднего значения мощности минимального разрещающего множества в классе %(Efy\ В подразделе 3.10.3 получены следствия из этих результатов, касающиеся специальных разбиений плоскости прямыми.
Пороговые булевы функции рассматриваются в разделе 3.11. Справедливо следующее равенство: т(Е) = т(Е) = \Е%\ = 2". В данном разделе также показано, что сложность расшифровки в классе пороговых монотонных булевых функций совпадает со сложностью расшифровки в классе монотонных булевых функций.
В разделе 3.12 полученные результаты о верхних и нижних оценках сложности расшифровки применяются к анализу оракульной сложности задачи о рюкзаке.
Результаты третьей главы диссертации опубликованы в работах [24, 26-28, 32, 33, 36, 109, 161]. В главе 4 показана связь задачи расшифровки пороговой функции двух переменных с проблемой нахождения диофантовых приближений вещественных чисел. Рассмотрим следующую задачу. Для а Є R, а 0, Q Є N требуется среди всех рациональных дробей со знаменателем, не превосходящим Q, найти наилучшее приближение - к а:
Предположим, что вещественное число а задано оракулом, позволяющим по произвольному г є Q определить, выполняется или нет неравенство а г. В разделе 4.2 показано, как использовать алгоритм s 2 для решения задачи наилучшего приближения к заданному таким образом числу. Время работы построенной процедуры ограничено полиномом от log к, где к = тах{(}, [#(?]}. В разделе 4.3 на основе полученных результатов строится полиномиальный алгоритм нахождения наилучших приближений алгебраических вещественных чисел, заданных минимальным многочленом.
Результаты четвертой главы диссертации опубликованы в работе [35].
В заключении обсуждаются основные результаты диссертации Глава 1 Свойства пороговых и близких к ним функций
В настоящей главе изучаются свойства функций, определенных на множестве целочисленных точек заданного /г-мерного выпуклого политопа и обладающих различными свойствами линейной отделимости. Результаты, полученные в [103] для Е%, распространяются в первых двух разделах на случай произвольного политопа. Определения изучаемых классов и некоторые простые свойства приведены в разделе 1.1. Величина коэффициентов характеристической системы, которая задает поверхность, разделяющую множества различных значений функции, исследуется в разделе 1.2. В разделе 1.3 выводятся оценки числа вершин выпуклой оболочки множеств «нулей» и «единиц» исследуемых функций. В разделах 1.4, 1.5 изучаются мощностные характеристики и соотношения исследуемых классов.
Расшифровка функций в классе F0(M) F1(M)
В ряде работ, например, [9, 130], предлагалось несколько способов добавления неравенств исходной системы в методе двойного описания. Каждый из них детерминирует правило выбора номера і на шаге 1.1 алгоритмов DDM и DDM.M1.
В методах minindex, lexmin, mincutoff, minpairs в качестве і выбираем соответственно 4iinindex = min /, iiexmin = arg lexmin {at: і Є 1} , 4iincutoff = argmin{U-\ : і є 1}, iminpairs = argmin{ U-\ -\U+\: і Є 1} .
Методы maxindex, lexmax, maxcutoff, maxpairs отличаются от рассмотренных тем, что в этих в формулах нужно заменить везде min и lexmin на max и lexmax соответственно. В методе random индекс / выбирается из множества /случайно равновероятно. Таким образом, метод mincutoff (соответственно, maxcutoff) на каждой итерации алгоритма минимизируют (соответственно, максимизирует) количество отсекаемых экстремальных лучей. Метод minpairs (соответственно, maxpairs) минимизируют (соответственно, максимизирует) количество рассматриваемых потенциально смежных пар.
Способы добавления неравенств можно условно разбить на две группы: 1) методы с фиксированным порядком неравенств; 2) методы с динамически определяемым порядком неравенств.
При первом способе порядок выбора неравенств может быть определен заранее до начала выполнения итераций. К таким методам относятся minindex, maxindex, lexmin, lexmax, random. В этом случае неравенства исходной системы Ах О можно отсортировать заранее и на шаге 1.1 считать, что і = min /.
Во втором случае номер і не может быть известен заранее. К методам с динамическим порядком относятся mincutoff, maxcutoff, minpairs, maxpairs.
В разделе 1.6.7 приведены некоторые результаты по экспериментальному сравнению рассмотренных методов добавления неравенств. 1.6.5. Методы проверки смежности экстремальных лучей
Здесь мы рассматриваем некоторые известные способы проверки на смежность экстремальных лучей конуса и предлагаем один новый метод. Необходимые и достаточные условия смежности лучей, приведенные далее, можно использовать как в исходном алгоритме DDM, так и в его модификации DDM.M1. Заметим, что на шаге 1.6 алгоритма DDM.M1 множество экстремальных лучей конуса {х є $п : Ajx О, aix 0}, принадлежащих Ц), совпадает со множеством всех экстремальных лучей конуса {х є $п : Ajx 0, а[Х =0}. Это обстоятельство имеет смысл учитывать при проверке описанных ниже тестов на смежность.
Пусть, как обычно, С = {х : Ах 0}, А є tfwxn, rank А = п и и Є $". Обозначим Z(u) = {і: А{и - 0}. Таким образом, Z(u) есть множество номеров ограничений системы Ах 0, активных для вектора и.
Хорошо известны два необходимых и достаточных условия для смежности экстремальных лучей конуса: «комбинаторный» и «алгебраический».
Утверждение 1.32 (Алгебраический тест). Пусть u,v Є U(C). Для того, чтобы {u,v} Є Е(С) необходимо и достаточно, чтобы rankAz(u)nZ(v) = п-2.
Утверждение 1.33 (Комбинаторный тест). Пусть u,v Є U(C). Для того, чтобы {u,v} Є Е(С) необходимо и достаточно, чтобы Z(u)r\Z(v) С Z(w) ни для какого we U(C)\{u,v}.
Алгебраический тест является следствием теоремы Минковского (см., например, [88]). Комбинаторный тест впервые предложен в работе [153], его доказательство приведено в [123].
Ранг в алгебраическом тесте можно вычислить с помощью общеизвестных алгоритмов линейной алгебры, что требует не более 0{тг?) арифметических операций. Таким образом, трудоемкость процедуры построения всех пар смежных лучей с помощью алгебраического теста составляет 0{тг? ), где 5= \U(C)\.
Из утверждения 1.32 получаем следующее простое необходимое условие смежности лучей.
Утверждение 1.34. Если {u,v} Є Е(С), тогда Z(u) П Z(v) п — 2. Сформулированное необходимое условие рассматривалось многими авторами, например, [9, 89, 123, 130, 146]. Многочисленные эксперименты показывают, что его разумно проверять всякий раз перед выполнением любого теста на смежность лучей.
Рассмотрим более подробно комбинаторный тест. Словестная его формулировка выглядит так: для того, чтобы экстремальные лучи и и v конуса С были смежны, необходимо и достаточно, чтобы неравенства, являющиеся активными для обоих лучей, не являлись одновременно активными ни для какого другого экстремального луча, иными словами, чтобы минимальная грань, содержащая оба вектора и и у, не содержала других экстремальных лучей. Последняя формулировка делает очевидным обоснование комбинаторного теста.
Выполнять комбинаторный тест удобно, имея в распоряжении матрицу Т = (tjj) Є {0,1}5ХЛЗ, в которой tfj = 1 тогда и только тогда, когда SjUf 0, где U = {«і, 1/2,..., us}. Для того, чтобы лучи щ и щ были смежны, необходимо и достаточно, чтобы для любого к є {1,2,..., s} \ {і, /} нашлось t, такое, что tie = tft = 0, tu - 1.
Трудоемкость проверки смежности двух лучей и и v составляет 0(ms) операций. Таким образом, трудоемкость процедуры построения всех пар смежных лучей с помощью комбинаторного теста есть 0(т). Мы предлагаем новую, «графовую», модификацию комбинаторного теста, которая позволяет существенно ускорить процедуру проверки смежности экстремальных лучей. Рассмотрим простой (неориентированный, без петель и кратных ребер) граф G, который построим по конусу С следующим образом. Множество вершин графа G есть множество U экстремальных лучей конуса С, а {и, v} образует ребро в G тогда и только тогда, когда \Z(u) П Z(v)\ п — 2. Множество всех ребер графа G обозначим E{G).
Оценки длины обучения в классе пороговых функций
Доказательство. Обозначим через R точку из Ф HZ2, лежащую на правильном отсечении вершины R\, ближайшую к RQ, а через R5 — точку из OfiZ2, лежащую на правильном отсечении вершины RQ, ближайшую к і?ь Вначале предположим, что R± Ф Rs (см. рис. 2.1 а). Так как Л RQR\RS, AR0R1R4 не содержат внутренних целочисленных точек, то по лемме 2.13 R0R1R4R5 — параллелограмм, следовательно, точки R4, R$ лежат на отрезках R1R2, R0R3 и не являются внутренними точками параллелограмма Ф. Очевидно, в этом случае Ф не содержит ни одной внутренней целочисленной точки.
Пусть теперь R± = R5 (см. рис. 2.16, в). Очевидно, что каждая из точек R4 = 2R4 — Ro и R5 = 2R5 — Ri имеет целочисленные координаты и по крайней мере одна из них в силу параллельности сторон R\Ri, R0R3
Доказательство. Вначале рассмотрим следующую вспомогательную процедуру. Предположим, что в концах отрезка [и, v] (и, v Є Ер х Eq), содержащем 5 внутренних целочисленных точек, значения функции f уже известны и f(u) Ф f(v). Процедура дихотомического поиска, находящая две соседние цело численные точки отрезка [и,г;], в которых функция /принимает различ и—и ные значения, заключается в следующем: положим w := и+ \д/2\ , Я где g — НОД компонент вектора v — и, и обратимся к оракулу в точке w, если f(u) = f(w), то u := w, иначе v := w, если u, v не являются соседними целочисленными точками, то найдем новое w и т. д. Очевидно, что описанная процедура завершается не более, чем за [log(s+ 1)] обращений к оракулу функции f. Заметим, что если і є N, 103 2і 5 2І+1, то і log 5 і+ 1 и і log(s+ 1) і+ 1. Отсюда при 5 Є N получаем: [log(s+ 1)] = [lg5J + 1 Перейдем теперь к пошаговому описанию алгоритма расшифровки функций из класса Х(Ер х Eq).
Шаг 0. Определим f(x) в вершинах прямоугольника ЕрхЕди обозначим через Sv (у = 0,1) множество тех из них, для которых f(x) = у. Если при у = 0 или при у = 1 множество Sv пусто, то расшифровка закончена, так как в этом случае Mv( /) = 0и/"=1— v.
Шаг 1. Пусть Li (і = 0,1) — сторона прямоугольника Ер х Eq, в концах которой функция / принимает различные значения. Дихотомией на каждой из сторон LQ, L\ найдем пару соседних целочисленных точек RQ, R\ И RI, Яъ соответственно, так, чтобы f(R0) = f(R3) = у, f(Ri) = f(R2) = 1 - У (У = 0,1). Присоединим Ro, R3 к Sv, a R\, R2 к Si-y. Для целочисленных точек из Conv Sv (у = 0,1) имеем f(x) = у. Если LQ И LI — противоположные стороны прямоугольника Ер х Eq, то RQ — R\ = R3 — Ri, следовательно, R0R1R2R3 — параллелограмм. В противном случае, когда LQ, L\ — смежные, обозначим через Re их общую вершину и рассмотрим ту пару точек R2i, Яц+\, которая расположена дальше от Re. Пусть JG{1,2}HVG {0,1} выбраны так, что Яц, Ru+i являются соседями по координате j и R +y расположена дальше от Re, чем Ru+i-y. Заменим R +y точкой R2i+y, соседней с Ru+i-v по координате 3 — j. Очевидно, что f(R2i+v) = Д- гя-у) И RQ — R\ = R3 — Ri- Положим \i\- 1, Rn+y := R2i+v Возможен случай, когда до замены обе пары RQ, RI И R2, R3 были равноудалены от Re, тогда, очевидно, Ф = RQRIR2R3 не содержит внутренних 104 целочисленных точек и Mv(f) = Conv Sv П (Ер х Eq) (у = 0,1) — расшифровка завершена.
Шаг 2. Алгоритмом g/J построим правильные отсечения вершин RQ И RI и выберем из них отсечение, проходящее через большее число точек из Ф П (Ер х Eg), где Ф = RoR\R2R3- Пусть і — номер соответствующей выбранному отсечению вершины, а 5ц — число лежащих на нем целочисленных внутренних точек области Ф. Если 5ц = 0, то по лемме 2.15 фигура Ф вообще не содержит внутренних целочисленных точек, Му( Г) = Conv Sv П (Ер х Eq) (у = 0,1) — расшифровка завершена. В противном случае дихотомией найдем две соседние целочисленные точки R0, RX, лежащие на построенном отсечении, такие, что ґ(К$) Ф f(K\). Аналогичную процедуру проведем с отсечением вершины і?з—у-дихотомией найдем лежащие на этом отсечении соседние целочисленные точки R2, R3, такие, что f(R ) = f(Rf3), Д- і) = Д-# ) (см. рис 2.2).
Шаг 3. Для всех і є {0,..., 3} положим Rj := Rt Добавим RQ И RT, К SV, a R\ и Ri к S\-y, где у = f(Ro). Увеличим ц на 1 и перейдем на шаг 2.
Очевидно, что за конечное число шагов алгоритм остановится, при этом Му( Г) = Conv Sv П Z2 — функция f расшифрована. Сами коэффициенты порогового неравенства можно вычислить алгоритмом, подобным процедуре из теоремы 2.5.
Связь задачи расшифровки с задачей приближения
Теперь перейдем к оценке коэффициентов cf , of систем неравенств, описывающих параллелепипеды в покрытии симплексов. Заметим, что метод построения покрытия, описанный в лемме 3.35, дает параллелепипеды, грани которых параллельны граням соответствующих симплексов, следовательно, коэффициенты левой части уравнений этих граней, т. е. коэффициенты матриц А \ удовлетворяют неравенству
Для оценивания bf \, \cf подставим координаты вершины у симплекса в уравнение грани. Из (3.16) и (3.17) вытекает Такое же неравенство справедливо и для с] \, откуда получаем (3.15). і 3.7.3. Неприводимые точки в политопе Здесь на основе результатов разделов 3.7.2, 3.7.1 мы получим оценку числа неприводимых целых точек в произвольном политопе.
Теорема 3.37. Пусть политоп Рзадан как множество решений системы неравенств Ах Ь, где А = {atj) Є Zmxn, b = (Ы) Є Zm, \atj\ a, \bt\ Д Пусть N — множество неприводимых точек в РГ\Хп, тогда \N\ 2n\Um){n+\)( nl2\ U + 2\og[\ + 2- n X . (3.18)
Доказательство. По лемме 3.36 построим покрытие политопа Рпарал лелепипедами. Очевидно, что N содержится в объединении множеств неприводимых целых точек во всех параллелепипедах. Оценить коли чество неприводимых точек в параллелепипеде позволяет теорема 3.33. Подставляя (3.15) в (3.6) и умножая полученный результат на г]п(ш) из (3.14), получаем неравенство (3.18). і Теорема 3.38. Пусть А є R xn, b Є R1 , Р= {х є R" : Ах Ь}, причем РГ\ Z" С Enk. Если N — множество неприводимых точек в РГ\Хп, тогда для \N\ справедливо неравенство (3.18), где т = я/ + 2д
Доказательство. Для неравенства ах ао, где а Є R", «зо Є R рассмотрим систему из к" + 1 однородных линейных неравенств относительно неизвестных Ьо Є R, Ь Є Rn, bn+\ Є R:
Множество К ее решений есть полиэдральный (многогранный) конус в R 2. Очевидно, что любой вектор, принадлежащий К, при Ьп+\ 0 имеет компоненты bo, b, bn+\, такие, что {х є Епк : ах ао} = {х є Г: Ьх Ьо}.
Докажем, что конус К острый, т. е. не содержит ненулевых подпространств. Предположим, что оба вектора ±(Ьо, b, Ьп+\) принадлежат К. Из последнего неравенства в (3.19) получаем тогда, что Ьп+\ = 0, откуда из остальных неравенств следует bx = bo для всех х є Епк. Так как к 2, то аффинная размерность множества Щ равна п, поэтому bo = b = bn+\ = 0. Итак, К не содержит ненулевых подпространств.
Из теории систем линейных неравенств (см., например, [88]) теперь вытекает, что множество экстремальных векторов gfl\ gf2\ ..., конуса К образует ее порождающую систему, т. е. К = Conej , ,... , 5)}. Более того, для каждого і = 1,2, ...,s найдется подсистема системы (3.19), обращающаяся на векторе в систему равенств, причем коэффициенты этой подсистемы образуют матрицу 7} ранга п + 1. Отсюда получаем, что ф может быть выбран целочисленным, причем его j-я компонента с точностью до знака будет равна минору (п+ 1)-го порядка, получающемуся вычеркиванием j-ro столбца из матрицы Г,.
В этом разделе предлагается алгоритм нахождения минимального разрешающего множества T(f) пороговой функции f є %{М), где М = РП Z", по известным коэффициентам порогового неравенства (1.2) и по известной системе, описывающей политоп Р. Далее будет показано, как изменить алгоритм &/\, чтобы сложность нового алгоритма з/ отличалась бы от сложности оптимального (по числу обращений к оракулу в худшем случае) алгоритма расшифровки не более, чем в О тг" log(/?y)) раз. Для класса X(Ef) сложность алгоритма &/ отличается от сложности оптимального алгоритма не более, чем в ОІуП2 \og(nkj) раз и при фиксированном п 2
Рассмотрим задачу 2 определения множеств Tv(f) (у = 0,1) для функции f є Х(М), М = PT\Zn, по заданным коэффициентам ао, а\,..., ап Є Z порогового неравенства (1.2) функции /и заданным коэффициентам целочисленной системы линейных неравенств, описывающей политоп Р. Пусть a = max {ао,..., ал}, тогда справедлива
Теорема 3.41. При любом фиксированном п существует полиномиальный от \oga, logy, 1 алгоритм решения задачи 2 Доказательство. Для решения задачи 2 с помощью алгоритма из леммы 1.21 найдем множества крайних точек No(f) и Ni(f). При фиксированном п это можно сделать с полиномиальной от log a, log у, 1 трудоемкостью. По лемме 3.10 Ty(f) С Nv(f) (у = 0,1), следовательно, для нахождения T(f) необходимо из системы (1.7) исключить все неравенства-следствия. Из утверждения 1.18 и леммы 1.7 следует, что число неравенств в системе (1.7) и коэффициенты этой системы при любом фиксированном п ограничены полиномами от І и log у. Для завершения доказательства теоремы осталось заметить, что выделить в (1.7) минимальную эквивалентную подсистему при фиксированном п можно за полиномиальное от І и logy число шагов (см. [81], а также раздел 1.6). і
По следствию 1.10 для любой f є %{М) существует такое пороговое неравенсто, что log а при фиксированном п ограничен полиномом от log у. При условии, что на вход задачи 2 подается пороговое неравенство, удовлетворяющее этому условию, алгоритм из теоремы 3.41 при любом фиксированном п полиномиален от log у и 1.
В алгоритме \ заменим шаг 2 на шаг 2 . Полученный таким образом алгоритм обозначим через &/.
Так как множество 7 = ц1 U ц является разрешающим для fh то процесс расшифровки заканчивается тогда и только тогда, когда f = 4 в противном случае найдется некоторый х є 7 , такой, что f(x) = 1 — у и итерация повторится.
Таким образом, алгоритм srf расшифровывает любую функцию из класса $+(М). Все оценки вычислительной трудоемкости и сложности переносятся на этот случай. Заметим, что на вход задачи 2 подаются рациональные коэффициенты а порогового неравенства, между тем, как в теореме 3.41 они должны быть целыми. Полученное пороговое неравенство, однако, домножением его коэффициентов на их наименьшее общее кратное легко преобразуется к требуемому виду. В обоих случаях длина двоичной записи этих коэффициентов при фиксированном п будет ограничена полиномом от І и log
Пусть ty(n, у) — множество политопов Р С W1, каждый из которых можно задать системой линейных неравенств с целочисленными коэффициентами, ограниченными по абсолютной величине числом у. Пусть &/ — оптимальный алгоритм расшифровки функций из класса %{М), т. е. т{. ) = т{М). Рассмотрим величину т{. )1т{М), показывающую, во сколько раз сложность алгоритма &/ отличается от сложности оптимального алгоритма &/ . Так как T( ) SmaKcr(M), где величина SmaK выражает верхнюю границу числа гипотез в алгоритме &/ и определяется формулой (2.10), и по утверждению 3.1 т{М) сг{М), то из (2.11) получаем
