Теория сложности вычислений. IX
Сборник работ под редакцией Э. А. ГИРША

ISSN 0373-2703
ISSN 0234-7482

Предисловие редактора

Настоящий том "Записок научных семинаров ПОМИ" продолжает серию "Теория сложности вычислений" и посвящается пятидесятилетию Дмитрия Юрьевича Григорьева, одного из первых редакторов и постоянного автора этой серии.

Тематика статей сборника отражает разносторонние математические интересы юбиляра. Статьи А. Айяда и В. Пана посвящены сложности алгоритмов для алгебраических задач (разложения многочлена на множители и вероятностного вычисления определителя); к этой же категории можно отнести и статью С. Басу, Р. Поллака и М.-Ф. Руа о вычислении размерности полуалгебраического множества. Несколько работ посвящено комбинаторной сложности: работа С. А. Евдокимова и И. Н. Пономаренко об ассоциативных схемах, работа В. Баргачева о перестановках, независимых относительно минимума, работа О. Финкеля, Ж.-П. Рессейра и П. Симоне о трассах. Статья Р. Патури и П. Пудлака предлагает новый метод доказательства нижних оценок для арифметических схем.

Четыре статьи посвящены задачам математической логики. Это статья Г. Минца и А. Кожевникова о системах доказательств для интуиционистской логики, статья В. П. Оревкова о новых разрешимых фрагментах исчисления предикатов, статья А. С. Куликова и С. С. Федина об автоматическом доказательстве оценок времени работы алгоритмов для задачи (максимальной) пропозициональной выполнимости и, наконец, статья В. Крейновича и А. М. Финкельштейна о логических описаниях физических теорий.

Э. А. Гирш