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

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

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



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






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


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

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

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

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

Л. А. Левин


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

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

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

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

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

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

Цитирование в формате 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{https://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

    ОТПРАВИТЬ: 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. М. Х. Айзенштейн, “О существовании оптимальных алгоритмов для комбинаторных задач и языков”, УМН, 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  isi
    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  isi
    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  elib; A. D. Korshunov, “Some unsolved problems in discrete mathematics and mathematical cybernetics”, Russian Math. Surveys, 64:5 (2009), 787–803  crossref  isi  elib
    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  isi
    9. С. И. Николенко, Д. С. Тугарëв, “Полная односторонняя функция, основанная на свободном $\mathbb Z\times\mathbb Z$-модуле конечного ранга”, Комбинаторика и теория графов. IV, Первый Российско-финский симпозиум по дискретной математике (специальный выпуск), Зап. научн. сем. ПОМИ, 402, ПОМИ, СПб., 2012, 91–107  mathnet  mathscinet; 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
    10. В. Н. Захаров, В. А. Козмидиади, “О соотношении классов сложности машин Тьюринга”, Ж. вычисл. матем. и матем. физ., 57:4 (2017), 730–743  mathnet  crossref  mathscinet  elib; V. N. Zakharov, V. A. Kozmidiadi, “On relationships between complexity classes of Turing machines”, Comput. Math. Math. Phys., 57:4 (2017), 726–738  crossref  isi
    11. Д. Е. Горбатенко, А. А. Семëнов, “Противодействие сговору в дискретных динамических моделях компьютерных сетей”, УБС, 75 (2018), 76–102  mathnet
  • Проблемы передачи информации Problems of Information Transmission
    Просмотров:
    Эта страница:5058
    Полный текст:3204
    Первая стр.:4

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