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

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

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


Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти




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

Дискретная математика, 1990, том 2, выпуск 1, страницы 142–154 (Mi dm844)  
О нижних оценках времени вычислений

Ю. И. Янов
PDF полного текста (1606 kB)
Аннотация: Вводится специальное представление предикатов с помощью полных систем признаков. Для определенного класса предикатов установлена связь их представлений с временем вычисления на машинах Тьюринга. Таким путем описан класс предикатов с квадратичной нижней оценкой временной сложности. Сформулирована гипотеза, утверждающая наличие подобной связи для существенно более широкого класса представлений. Принятие этой гипотезы дает для соответствующих предикатов экспоненциальную нижнюю оценку временной сложности.
Статья поступила: 27.06.1989
Реферативные базы данных:
УДК: 519.71
Образец цитирования: Ю. И. Янов, “О нижних оценках времени вычислений”, Дискрет. матем., 2:1 (1990), 142–154; Discrete Math. Appl., 1:4 (1991), 391–403
Цитирование в формате AMSBIB
\RBibitem{Yan90}
\by Ю.~И.~Янов
\paper О~нижних оценках времени вычислений
\jour Дискрет. матем.
\yr 1990
\vol 2
\issue 1
\pages 142--154
\mathnet{http://mi.mathnet.ru/dm844}
\mathscinet{https://mathscinet.ams.org/mathscinet-getitem?mr=1053512}
\zmath{https://zbmath.org/?q=an:0790.68047|0724.68042}
\transl
\jour Discrete Math. Appl.
\yr 1991
\vol 1
\issue 4
\pages 391--403
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/dm844
  • https://www.mathnet.ru/rus/dm/v2/i1/p142
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретная математика
    Статистика просмотров:
    Страница аннотации:426
    PDF полного текста:163
    Список литературы:2
    Первая страница:3
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025