RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Изв. РАН. Сер. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Изв. РАН. Сер. матем., 1993, том 57, выпуск 2, страницы 51–90 (Mi izv878)  

Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)

Релятивизуемые и нерелятивизуемые теоремы полиномиальной теории алгоритмов

Н. К. Верещагин

Институт новых технологий

Аннотация: Начиная с работы Бейкера, Гилла и Соловея [6], в теории вычислительной сложности был доказан ряд результатов, состоящих в отделении различных релятивизованных классов сложности или в несуществовании в таких классах полных языков. При этом все результаты такого сорта, по существу, были основаны на получении нижних оценок для разрешающих деревьев специального вида или машин с полилогарифмическим ограничением на время работы. Возникает вопрос: являются ли эти методы доказательства “релятивизованных” результатов универсальными? Первая часть настоящей работы как раз и состоит в том, что предлагается общая модель, в которой утверждения об универсальности такого рода можно сформулировать и доказать в виде удобных критериев. Эти критерии позволяют получить в качестве простых следствий некоторых известных результатов о булевских разрешающих деревьях некоторые новые “релятивизованные” результаты, а также новые доказательства некоторых старых результатов. Вторая часть работы состоит в применении найденных общих критериев к большому числу частных случаев. Например, для большого числа ранее изучавшихся в литературе классов полностью описаны все релятивизуемые включения между этими классами.

Полный текст: PDF файл (2167 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Russian Academy of Sciences. Izvestiya Mathematics, 1994, 42:2, 261–298

Реферативные базы данных:

УДК: 510.52
MSC: 68Q15
Поступило в редакцию: 16.03.1990
Исправленный вариант: 18.11.1991

Образец цитирования: Н. К. Верещагин, “Релятивизуемые и нерелятивизуемые теоремы полиномиальной теории алгоритмов”, Изв. РАН. Сер. матем., 57:2 (1993), 51–90; Russian Acad. Sci. Izv. Math., 42:2 (1994), 261–298

Цитирование в формате AMSBIB
\RBibitem{Ver93}
\by Н.~К.~Верещагин
\paper Релятивизуемые и нерелятивизуемые теоремы полиномиальной теории алгоритмов
\jour Изв. РАН. Сер. матем.
\yr 1993
\vol 57
\issue 2
\pages 51--90
\mathnet{http://mi.mathnet.ru/izv878}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1230967}
\zmath{https://zbmath.org/?q=an:0822.68035}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?1994IzMat..42..261V}
\transl
\jour Russian Acad. Sci. Izv. Math.
\yr 1994
\vol 42
\issue 2
\pages 261--298
\crossref{https://doi.org/10.1070/IM1994v042n02ABEH001537}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=A1994NT25700002}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/izv878
  • http://mi.mathnet.ru/rus/izv/v57/i2/p51

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. P. Cintioli, R. Silvestri, “Helping by unambiguous computation and probabilistic computation”, Theory Comput Systems, 30:2 (1997), 165  crossref  mathscinet  zmath  isi
    2. Bernd Borchert, Riccardo Silvestri, “A characterization of the leaf language classes”, Information Processing Letters, 63:3 (1997), 153  crossref
    3. Helmut Veith, “Succinct Representation, Leaf Languages, and Projection Reductions”, Information and Computation, 142:2 (1998), 207  crossref
    4. Lance Fortnow, John Rogers, “Complexity Limitations on Quantum Computation”, Journal of Computer and System Sciences, 59:2 (1999), 240  crossref
    5. LANE A. HEMASPAANDRA, HARALD HEMPEL, GERD WECHSUNG, “SELF-SPECIFYING MACHINES”, Int. J. Found. Comput. Sci, 10:03 (1999), 263  crossref
    6. Bernd Borchert, Riccardo Silvestri, “Dot operators”, Theoretical Computer Science, 262:1-2 (2001), 501  crossref
    7. Lane A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung, “Reducing the Number of Solutions of NP Functions”, Journal of Computer and System Sciences, 64:2 (2002), 311  crossref
    8. Holger Spakowski, Rahul Tripathi, “LWPP and WPP are not uniformly gap-definable”, Journal of Computer and System Sciences, 72:4 (2006), 660  crossref
  • Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Просмотров:
    Эта страница:282
    Полный текст:86
    Литература:25
    Первая стр.:2

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018