close

Вход

Забыли?

вход по аккаунту

?

О генерической сложности экзистенциальных теорий.

код для вставкиСкачать
МАТЕМАТИКА
Вестн. Ом. ун-та. 2016. № 4. С. 6–9.
УДК 510.52
А.Н. Рыбалов
О ГЕНЕРИЧЕСКОЙ СЛОЖНОСТИ
ЭКЗИСТЕНЦИАЛЬНЫХ ТЕОРИЙ*
Рассматривается генерический подход к алгоритмическим проблемам, предложенный в 2003 г. Мясниковым, Каповичем, Шуппом и Шпильрайном. В рамках этого
подхода алгоритмическая проблема рассматривается не для всего множества входов
(сложность в худшем случае), а для множества «почти всех» входов. Термин «почти
все входы» уточняется при помощи введения естественной меры на множестве входных данных. В статье доказывается, что любая неразрешимая экзистенциальная теория остается неразрешимой на любом рекурсивном генерическом множестве экзистенциальных формул.
Ключевые слова: генерическая сложность, экзистенциальные теории.
Введение
Теория алгоритмов в классической постановке изучает алгоритмические проблемы в худшем случае, рассматривая поведение алгоритмов на
всём множестве входов. В Computer Science исследуется также сложность
алгоритмов в среднем, при этом алгоритм может хорошо (полиномиально)
работать на большинстве входных данных и плохо (экспоненциально) – на
очень редких входах. Генерический подход в применении к алгоритмическим проблемам был впервые предложен в статье 2003 года [1]. В рамках
этого подхода изучается поведение алгоритмов на множестве «почти всех»
входов (это множество называется генерическим), игнорируя поведение
алгоритма на остальных входах, на которых алгоритм может работать медленно или вообще не останавливаться. Такой подход имеет приложение в
криптографии, где требуется, чтобы алгоритмические проблемы были
трудными для «почти всех» входов. В отличие от сложности в среднем, генерический подход применим и для алгоритмически неразрешимых проблем. Для многих классических алгоритмически неразрешимых проблем
алгебры доказано, что они разрешимы в генерическом случае. Например,
в работе [2] установлено, что проблема остановки для машин Тьюринга с
полубесконечной лентой генерически разрешима.
Большой пласт алгоритмических проблем связан с проблемами разрешения элементарных теорий различных алгебраических систем. Как правило, эти проблемы либо неразрешимы (формальная арифметика, теория
поля рациональных чисел, теория графов и т. д.), либо разрешимы, но
имеют очень высокую вычислительную сложность (арифметика Пресбургера, теория упорядоченного поля действительных чисел и т. д.). Поэтому
представляет интерес изучение их генерической разрешимости и сложности. А. Рыбалов и А. Мясников в своей работе [3] доказали, что любая неразрешимая в классическом смысле элементарная теория остается неразрешимой на строго генерических множествах формул. Также представляет
интерес изучение в рамках генерического подхода фрагментов элементарных теорий различных алгебраических систем, например, их экзистенциальных теорий. Например, из знаменитой теоремы Дэвиса, Робинсон, Патнема и Матиясевича [4] о неразрешимости десятой проблемы Гильберта
следует, что эта теория неразрешима. В данной работе доказывается, что
любая неразрешимая в классическом смысле теория остается неразрешимой на любом рекурсивном генерическом множестве экзистенциальных
формул. При этом используется так называемое нормализованное пред*
Работа выполнена при финансовой поддержке РФФИ (16-01-00577).
© Рыбалов А.Н., 2016
О генерической сложности экзистенциальных теорий
ставление формул, которое подразумевает
упорядоченность нумерации переменных в
формуле слева направо: вторая переменная
не может встретиться раньше (левее) первой,
третья – раньше второй и т. д. Это довольно
естественное требование, ведь если человека
попросить написать случайную формулу, он
не станет сразу использовать x100 , а начнет с
x1 и будет вводить новые переменные по
мере надобности.
Генерическая вычислимость и сложность
Пусть A есть множество всех входов для
некоторой алгоритмической проблемы, а S –
некоторое его подмножество. Рассмотрим
последовательность
n ( S ) 
где
An
| S An |
,
| An |
– множество всех входов проблемы
размера n . Если случайно и равновероятно
генерировать входы размера n , то вероятность попасть в S равна n ( S ) . Определим
асимптотическую плотность множества S
как предел (если он существует)
(S )  lim n ( S ).
n 
Если предела не существует, то считаем,
что асимптотическая плотность неопределена.
Множество входов S  A называется генерическим, если (S )  1 , и пренебрежимым, если
(S )  0 . Непосредственно из
определения следует, что S является генерическим тогда и только тогда, когда A \ S пренебрежимо. Понятие генерического множества формализует интуитивное понятие множества «почти всех» входов в том смысле, что
при увеличении размера входа вероятность
того, что случайно сгенерированный вход попадет в генерическое множество, стремится
к 1. Если последовательность n ( S ) стремится к 0 экспоненциально быстро, т. е. существуют константы C  0 и 0    1 такие,
что для любого n
n (S )  Cn ,
то множество S называется строго пренебрежимым. Строго пренебрежимое множество существенно меньше просто пренебрежимого в том смысле, что никакое (не строго)
пренебрежимое множество не может содержаться в строго пренебрежимом. Множество
S называется строго генерическим, если
A \ S строго пренебрежимо.
Алгоритмическая проблема S  A генерически разрешима, если существует множество G  A такое, что
7
G – генерическое.
G – разрешимо.
S G – разрешимо.
Генерический алгоритм, решающий проблему S , работает следующим образом. Сначала определяет, принадлежит ли вход генерическому множеству. Если да, то проверяет
принадлежность входа S . Если нет, то отвечает «НЕ ЗНАЮ». Такой алгоритм правильно
решает проблему S на почти всех входах.
Представление
экзистенциальных
формул
В этой статье мы рассмотрим некоторое
естественное представление замкнутых экзистенциальных формул языка первого порядка с помощью двоичных деревьев. Это
представление, с одной стороны, настолько
же компактно, как и стандартное представление строками символов (с точностью до линейного множителя). С другой стороны, оно
удобно для различного рода подсчетов.
Зафиксируем конечную сигнатуру


  P1a1 ,..., Pkak , f1b1 ,..., f mbm , c1 ,..., cl ,
где Pi – предикаты, f i – функции и ci – константы.
Положим
Пусть   A, 
K  K  max ai , b j   1 .
– алгебраическая система
сигнатуры  . Назовем замкнутую формулу
 сигнатуры  простой атомарной, если
она имеет следующий вид:
1. x j  fi ( xi1 ,..., xis ) ,
2. Pi ( xi1 ,..., xir ) ,
3. xi  x j ,
4. xi  c j .
Мы говорим, что замкнутая экзистенциальная формула  сигнатуры  имеет
натуральную пренексную форму, если она
имеет вид:
  x1...xt  ,
где  – бескванторная формула, полученная
с помощью конъюнкций, дизъюнкций из
простых атомарных формул или их отрицаний. Заметим, что любая замкнутая экзистенциальная формула может быть приведена с помощью эквивалентных преобразований к натуральной пренексной форме.
При этом размер формулы увеличивается не
более чем линейно.
Пусть теперь  – бескванторная формула, которая является булевой комбинацией
простых атомарных формул и их отрицаний.
Естественным образом можно сопоставить
формуле  бинарное дерево T , которое
представляет конструкцию  из простых
8
А.Н. Рыбалов
атомарных формул и их отрицаний с помощью конъюнкций и дизъюнкций. Внутренние вершины T помечены символами
 , а листья T

и
помечены простыми атомар-
ными или их отрицаниями. С другой стороны, по любому такому бинарному дереву
можно восстановить бескванторную формулу. Это дает взаимно-однозначное представление бескванторных частей замкнутых
формул сигнатуры  в натуральной пренексной форме размеченными бинарными деревьями. Если T имеет т листьев, то не более Kn переменных могут встретиться в T ,
поэтому в дальнейшем будем полагать, что
все переменные
x1 ,..., xKn .
T лежат в множестве
Кроме того, считаем, что на все
Kn переменных навешаны кванторы.
Будем называть дерево T нормализованным, если для любой переменной xi , i  1
число Каталана. Каждая внутренняя вершина может быть помечена либо  , либо 
(всего n  1 таких вершин – 2
вариантов
разметки). Обозначим через Li число спосоn1
бов разметки i-го листа (нумерация листов
дерева слева направо). В итоге получается
Fn  L1...Ln 2n1 Cn 1 .
Теперь посчитаем число формул размера
n из множества eq() . Это делается аналогично, с той лишь разницей, что там у формул произвольной может быть лишь поддерево, отвечающее за формулу  . Оно имеет
n  t  1 листьев, листья могут быть размечены Lt  2 ,..., Ln способами. Кроме того, произвольными могут быть кванторные приставки QK (t  2) ,..., QKn . Итого
eq()n  Lt  2 ...Ln 2nt 2 Cn t 2 .
Оценим теперь асимптотическую плотность множества eq() :
найдется переменная xi 1 , расположенная
либо в том же листе дерева, либо в более ле-
  eq()   lim
вом. Заметим, что любое дерево T можно
 lim
n 
часть  формулы  . Мы будем отождествлять формулу  с её представлением. Размер
формулы  – это количество листьев дерева
T .
Для любой формулы   x1...xt  рассмотрим множество формул
eq() 
 x1...xt Qt 1 xt 1...xKn (  (( x1  x1 )  )) ,
где n  t – любое,  – произвольная бескванторная формула от переменных
x1 ,..., xn .
Легко видеть, что все формулы из eq() эквивалентны  в том смысле, что они истинны или ложны одновременно с  .
Лемма 1. Для любой формулы  множество eq() не является пренебрежимым.
Доказательство. Обозначим через F –
множество всех экзистенциальных формул и
через Fn – множество всех таких формул размера n . Любая формула размера n , состоит
из бинарного дерева с n листьями и n  1 -й
внутренней вершиной. Существуют Cn 1
неизоморфных бинарных деревьев с n листьями, где Cn 1 
1  2(n  1) 

 – это n  1 -е
n  n 1 
Fn

Lt  2 ...Ln 2n t  2 Cn t  2

n 
L1...Ln 2n 1 Cn 1
Cn t  2
 lim

t 1
n  L ...L
Cn 1
1
t 1 2
нормализовать подходящей перестановкой
переменных.
Таким образом представление экзистенциальной формулы  состоит из бинарного
дерева T , представляющего бескванторную
eq()n

1
4n t  2 (n  1)3/ 2
lim
 const  0.
t 1 n 
L1...Lt 1 2
(n  t  2)3/ 2 4n 1
Здесь использована асимптотика чисел
Каталана Cn ~
4n
n3/ 2 
(см. [5]). Также исполь-
зовано то, что число способов разметить лист
Li , i  t  const , является константой – это
следует из нормализованности представления формул. Лемма доказана.
Основной результат
Теорема 1. Если экзистенциальная тео-
рия Th   неразрешима, то Th   не является генерически разрешимым.
Доказательство. Допустим, что Th  
генерически разрешима. Это значит, что существует разрешимое генерическое множе-
ство формул G такое, что Th    G разрешимо. Покажем, что тогда и вся Th   будет разрешимой. Разрешающий алгоритм
для Th   будет работать на формуле 
следующим образом. Перебираем формулы
из множества eq() в возрастающем порядке до тех пор, пока не получим формулу
из G . Это обязательно произойдет, потому
О генерической сложности экзистенциальных теорий
что множество eq() , по лемме 1, не пренебрежимо, а множество G генерическое. Попав в G , решаем проблему истинности для
eq() , а тем самым, и проблему истинности
для  . Полученное противоречие доказывает теорему.
ЛИТЕРАТУРА
[1] Karpovich A. V., Myasnikov A. G., Schupp P.,
Shpilrain V. Generic-case complexity, decision
problems in group theory and random walks // J. Algebra. 2003. Vol. 264. № 2. P. 665–694.
9
[2] Hamkins J. D., Miasnikov A. The halting problem is
decidable on a set of asymptotic probability one //
Notre Dame Journal of Formal Logic. 2006.
Vol. 47. № 4. P. 515–524.
[3] Myasnikov A., Rybalov A. Generic complexity of
undecidable problems // Journal of Symbolic Logic.
2008. Vol. 73. № 2. Р. 656–673.
[4] Матиясевич Ю. В. Диофантовость перечислимых множеств // Доклады Академии наук СССР.
1970. Т. 191. № 2. С. 279–282.
[5] Кнут Д., Грэхем Р., Паташник О. Конкретная
математика. Математические основы информатики. М. : Вильямс, 2009. 784 с.
Документ
Категория
Без категории
Просмотров
4
Размер файла
1 467 Кб
Теги
генерической, сложности, теория, экзистенциальная
1/--страниц
Пожаловаться на содержимое документа