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

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

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



Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти



Поиск по сайту:
Найти



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


Пробл. передачи информ., 1973, том 9, выпуск 3, страницы 115–116 (Mi ppi914)  

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

Краткие сообщения


PDF версия     HTML версия

Универсальные задачи перебора

Л. А. Левин


Аннотация: В статье рассматривается несколько известных массовых задач “переборного типа” и доказывается, что эти задачи можно решать лишь за такое время, за которое можно решать вообще любые задачи указанного типа.

УДК: 519.14

Поступила в редакцию: 07.06.1972

Образец цитирования: Л. А. Левин, “Универсальные задачи перебора”, Пробл. передачи информ., 9:3 (1973), 115–116

Цитирование в формате AMSBIB
\RBibitem{Lev73}
\by Л.~А.~Левин
\paper Универсальные задачи перебора
\jour Пробл. передачи информ.
\yr 1973
\vol 9
\issue 3
\pages 115--116
\mathnet{http://mi.mathnet.ru/ppi914}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=340042}
\zmath{http://zbmath.org/?q=an:0313.02026}
\transl
\jour Problems Inform. Transmission
\yr 1973
\vol 9
\issue 3
\pages 265--266


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ppi914
  • http://mi.mathnet.ru/rus/ppi/v9/i3/p115

    Полный текст: PDF файл (306 kB)

    Англоязычная версия:
    Problems of Information Transmission, 1973, 9:3, 265–266

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

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


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

    Эта публикация цитируется в следующих статьяx:
    1. М. Х. Айзенштейн, “О существовании оптимальных алгоритмов для комбинаторных задач и языков”, УМН, 35:5(215) (1980), 221–222  mathnet  mathscinet  zmath  adsnasa; M. Kh. Aizenshtein, “On the existence of optimal algorithms for combinatorial problems and languages”, Russian Math. Surveys, 35:5 (1980), 249–250  crossref
    2. А. О. Слисенко, “Сложностные задачи теории вычислений”, УМН, 36:6(222) (1981), 21–103  mathnet  mathscinet  zmath  adsnasa; A. O. Slisenko, “Complexity problems in computational theory”, Russian Math. Surveys, 36:6 (1981), 23–125  crossref
    3. П. Витаньи, М. Ли, “Колмогоровская сложность: двадцать лет спустя”, УМН, 43:6(264) (1988), 129–166  mathnet  mathscinet  zmath
    4. Л. А. Левин, “Односторонние функции”, Пробл. передачи информ., 39:1 (2003), 103–117  mathnet  mathscinet  zmath; L. A. Levin, “One-Way Functions”, Problems Inform. Transmission, 39:1 (2003), 92–103  crossref
    5. V. Kreinovich, M. Margenstern, “In some curved spaces, one can solve NP-hard problems in polynomial time”, Исследования по конструктивной математике и математической логике. XI, Зап. научн. сем. ПОМИ, 358, ПОМИ, СПб., 2008, 224–250  mathnet  elib; J. Math. Sci. (N. Y.), 158:5 (2009), 727–740  crossref
    6. Э. А. Гирш, Д. Ю. Григорьев, К. В. Первышев, “Иерархии по времени с неравномерной подсказкой для криптографического обращения функций”, Исследования по конструктивной математике и математической логике. XI, Зап. научн. сем. ПОМИ, 358, ПОМИ, СПб., 2008, 54–76  mathnet; E. A. Hirsch, D. Yu. Grigor'ev, K. V. Pervyshev, “Time hierarchies for cryptographic function inversion with advice”, J. Math. Sci. (N. Y.), 158:5 (2009), 633–644  crossref
    7. А. Д. Коршунов, “Некоторые нерешенные задачи дискретной математики и математической кибернетики”, УМН, 64:5(389) (2009), 3–20  mathnet  crossref  mathscinet  zmath  adsnasa; A. D. Korshunov, “Some unsolved problems in discrete mathematics and mathematical cybernetics”, Russian Math. Surveys, 64:5 (2009), 787–803  crossref
    8. А. А. Кожевников, С. И. Николенко, “О полных односторонних функциях”, Пробл. передачи информ., 45:2 (2009), 101–118  mathnet  mathscinet  zmath; A. A. Kozhevnikov, S. I. Nikolenko, “On complete one-way functions”, Problems Inform. Transmission, 45:2 (2009), 168–183  crossref
    9. С. И. Николенко, Д. С. Тугарëв, “Полная односторонняя функция, основанная на свободном $\mathbb Z\times\mathbb Z$-модуле конечного ранга”, Комбинаторика и теория графов. IV, Первый Российско-финский симпозиум по дискретной математике (специальный выпуск), Зап. научн. сем. ПОМИ, 402, ПОМИ, СПб., 2012, 91–107  mathnet; S. I. Nikolenko, D. S. Tugaryov, “A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module”, J. Math. Sci. (N. Y.), 192:3 (2013), 307–315  crossref
  • Проблемы передачи информации Problems of Information Transmission
    Просмотров:
    Эта страница:2171
    Полный текст:980
    Первая стр.:4

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