Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 20»

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК 20 Сборник переводов ПОД РЕДАКЦИЕЙ О. Б. ЛУПАНОВА МОСКВА «МИР» 1983 ББК 32. 81 К38 УДК 519. 95 Научный совет по кибернетике Академии Наук СССР Кибернетический^сборник. Новая серия. Вып. 20. Сб. статей: Пер. с англ. — М. : Мир, 1983, 224 с, ил. Продолжение серии, начатой издательством «Мир» в 1965 г. В выпуске содержатся обзорные статьи и оригинальные работы известных зарубежных уче- ученых по наиболее актуальным проблемам теоретической кибернетики. Большой интерес представляют статьи Д. Маллера и Ф. Препараты по проблемам вычис- вычислительной геометрии, Г. Льюиса по теории сложности вычислений и цикл работ по сложности вычисления многочленов (Ф. Штрассен, К. Шнорр и др. ). Для научных работников, инженеров-исследователей, аспирантов и студен- студентов, занимающихся и интересующихся теоретической кибернетикой и ее прило- приложениями. Редакция литературы по математическим наукам КИБЕРНЕТИЧЕСКИЙ СБОРНИК Новая серия Выпуск 20 Ст. научн. ред. Г. М. Ильичева. Мл. научн. ред. Р. И. Пяткина. Художник Н. К. Са- Сапожников. Художественный редактор В. И. Шаповалов. Технический редактор Н. И. Манохина. Корректор Е. Г. Литвак И Б 3563 Сдано в набор 22. 12. 82. Подписано к печати 23. 09. 83. Формат 69Х9Э'/16. Объем бум. л. 7. Бумага типографская № 2. Гарнитура литературная. Печать высокая. Усл. печ. л. 14. Усл. кр. -отт. 14. Уч. изд. л. 13,41. Изд. № 1/2648. Тираж 3500 экз. Зак. 560. Цена 2 р. 10 к. ИЗДАТЕЛЬСТВО «МИР» 129820, Москва, И-110, ГСП, 1-й Рижский пер. , 2. Ленинградская типография № 2 головное предприятие ордена Трудового Красного Зна- Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Союз- полпграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли. 198052, г. Ленинград, Л-52, Измайловский проспект, 29. Отпечатано с набора в Ленинградской типографии № 8 ордена Трудового Красного Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Союзполиграфпрома при Государственном комитете СССР по делам издательств, поли- полиграфии и книжной торговли. 190000 Ленинград. Прачечный переулок, 6. © «Мир», 1983 СОДЕРЖАНИЕ Д. MA Л Л ЕР, Ф. ПРЕПАРАТА. Нахождение пересечения двух выпуклых многогранников. Перевод О. М. Касим-Заде 5 К. ШНОРР. Улучшенные нижние оценки числа умножений/делений, необ- ■ ходимых для вычисления многочленов. Перевод О. М. Касим-Заде ... 30 И. ХАИНЦ, М. ЗИВЕКИНГ. Нижние оценки для многочленов с алгеб- алгебраическими коэффициентами. Перевод О. М. Касим-Заде 46 И. ФОН ЦУР ГАТЕН, Ф. ШТРАССЕН. Некоторые многочлены, имеющие высокую сложность вычисления. Перевод О. М. Казим-Заде 59 Г. ЛЬЮИС. Сложностные результаты для классов формул с кванторами. Перевод С. В. Попова 64 В. ПАУЛЬ, Э. ПРАУСС, Р. РАИШУК. Об альтернировании. I. Перевод Л. Л. Мучника 107 В. ПАУЛЬ, Р. РАЙШУК. Об альтернировании. II. Перевод Л. А. Мучника 123 А. А. МУЧНИК. Добавление переводчика к статьям «Об альтернирова- альтернировании, I, II» 141 ДЖ. ДОИЛ. Система поддержания истинности. Перевод JI. И. Танен- гольца 159 ДЖ.