Избранные вопросы теории сложности вычислений

1. Схемы в полном базисе, оценка , класс P/poly, теорема Сэйведжа.

2. Проблема P=?NP и теорема Карпа-Липтона.

3. Верхние оценки для размера и глубины схем, вычисляющих конкретные функции:

• 
  а) PARITY, , .
  
• 
  б) Сложение натуральных чисел, , .
  
• 
  в) MAJORITY, , .
  
• 
  г) Умножение натуральных чисел:  , .
  

5. Формулы.

• 
  а) Теорема Spira-Храпченко о связи размера формулы и глубины схемы.
  
• 
  б) Лемма Субботовской.
  
• 
  в) Нижняя оценка формульной сложности функции Андреева в стандартном базисе.
  
• 
  г) Теорема Нечипорука-Патерсона-Цвика.
  
• 
  д) Нижняя оценка для функции различения и функции Андреева в полном базисе.
  
• 
  е) Теорема Храпченко и нижняя оценка формульной сложности функций PARITY, MAJORITY.
  
• 
  ж) Теорема Карчмера-Вигдерсона.
  

• 
  а) построение оракулов, относительно которых P=NP и P≠NP: теорема Бейкера, Гилла и Соловея.
  
• 
  б) сведение проблемы оракульного отделения PSPACE от PH и от к получению нижних оценок для схем ограниченной глубины.
  
• 
  в) Лемма Хостада.
  
• 
  г) Экспоненциальная нижняя оценка размера схемы глубины d, вычисляющей функции PARITY, MAJORITY.
  

8. Ветвящиеся программы, контактно-вентильные схемы, связь со сложностью вычислений на машинах Тьюринга.

• 
  а) NP^сс со – NP^сс = P^сс.
  
• 
  б) Пример функции с полиномиальным разрывом вероятностной и детерминированной сложностей.
  
• 
  в)BPP^dt = P^dt.
  

• 
  а) NP^сс со – NP^сс = P^сс.
  
• 
  б) Быстрый вероятностный алгоритм распознавания отношения равенства.
  
• 
  в) Нижняя оценка детерминированной сложности отношения равенства.
  

• 
  а) Определение.
  
• 
  б) PSPACEIP.
  
• 
  в) MIP=OP.
  
• 
  г) NEXP=OP (включение слева направо – без доказательства).