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

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

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



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






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


Матем. заметки, 1971, том 10, выпуск 1, страницы 83–92 (Mi mz7071)  

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

Об одном методе получения нижних оценок сложности $\Pi$-схем

В. М. Храпченко

Институт прикладной математики АН СССР

Аннотация: Излагается способ получения квадратичных (относительно числа аргументов функции) нижних оценок для сложности $\Pi$-схем. Библ. 2 назв.

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

Англоязычная версия:
Mathematical Notes, 1971, 10:1, 474–479

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

УДК: 51.0116
Поступило: 27.07.1970

Образец цитирования: В. М. Храпченко, “Об одном методе получения нижних оценок сложности $\Pi$-схем”, Матем. заметки, 10:1 (1971), 83–92; Math. Notes, 10:1 (1971), 474–479

Цитирование в формате AMSBIB
\RBibitem{Khr71}
\by В.~М.~Храпченко
\paper Об одном методе получения нижних оценок сложности $\Pi$-схем
\jour Матем. заметки
\yr 1971
\vol 10
\issue 1
\pages 83--92
\mathnet{http://mi.mathnet.ru/mz7071}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=287982}
\zmath{https://zbmath.org/?q=an:0223.68009}
\transl
\jour Math. Notes
\yr 1971
\vol 10
\issue 1
\pages 474--479
\crossref{https://doi.org/10.1007/BF01747074}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mz7071
  • http://mi.mathnet.ru/rus/mz/v10/i1/p83

    ОТПРАВИТЬ: 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. А. О. Слисенко, “Сложностные задачи теории вычислений”, УМН, 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
    2. A. A. Razborov, “Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic”, Изв. РАН. Сер. матем., 59:1 (1995), 201–224  mathnet  mathscinet  zmath; Izv. Math., 59:1 (1995), 205–227  crossref  isi
    3. К. Л. Рычков, “О связи нижних оценок сложности схем из функциональных элементов с задачей о минимальном покрытии”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 9:1 (2002), 54–58  mathnet  mathscinet  zmath
    4. К. Л. Рычков, “О сложности обобщённых контактных схем”, Дискретн. анализ и исслед. опер., 16:5 (2009), 78–87  mathnet  mathscinet  zmath
    5. В. Б. Кудрявцев, А. Е. Андреев, “О сложности алгоритмов”, Фундамент. и прикл. матем., 15:3 (2009), 135–181  mathnet  mathscinet; V. B. Kudryavtsev, A. E. Andreev, “On algorithm complexity”, J. Math. Sci., 168:1 (2010), 89–122  crossref  elib
    6. К. Л. Рычков, “Нижняя оценка сложности реализации в классе $\pi$-схем $q$-ичного счётчика кратности $q$”, Дискретн. анализ и исслед. опер., 17:6 (2010), 68–76  mathnet  mathscinet  zmath
    7. А. Д. Коршунов, “Сложность вычислений булевых функций”, УМН, 67:1(403) (2012), 97–168  mathnet  crossref  mathscinet  zmath  adsnasa  elib; A. D. Korshunov, “Computational complexity of Boolean functions”, Russian Math. Surveys, 67:1 (2012), 93–165  crossref  isi  elib
    8. С. В. Августинович, Ю. Л. Васильев, К. Л. Рычков, “Формульная сложность тернарной линейной функции”, Дискретн. анализ и исслед. опер., 19:3 (2012), 3–12  mathnet  mathscinet; S. V. Avgustinovich, Yu. L. Vasil'ev, K. L. Rychkov, “The computation complexity in the class of formulas”, J. Appl. Industr. Math., 6:4 (2012), 403–409  crossref
    9. Ю. Л. Васильев, К. Л. Рычков, “Нижняя оценка формульной сложности тернарной линейной функции”, Дискретн. анализ и исслед. опер., 20:4 (2013), 15–26  mathnet  mathscinet; Yu. L. Vasil'ev, K. L. Rychkov, “A lower bound on formula size of a ternary linear function”, J. Appl. Industr. Math., 7:4 (2013), 588–596  crossref
    10. В. М. Храпченко, “Упрощенное доказательство одной нижней оценки сложности”, Дискрет. матем., 25:2 (2013), 82–84  mathnet  crossref  mathscinet  elib; V. M. Khrapchenko, “A simplified proof of a lower complexity estimate”, Discrete Math. Appl., 23:2 (2013), 171–174  crossref
    11. И. С. Сергеев, “Верхние оценки сложности формул для симметрических булевых функций”, Изв. вузов. Матем., 2014, № 5, 38–52  mathnet; I. S. Sergeev, “Upper bounds on the formula size of symmetric Boolean functions”, Russian Math. (Iz. VUZ), 58:5 (2014), 30–42  crossref
    12. С. Б. Гашков, Е. Т. Шавгулидзе, “О представлении произведений в виде суммы степеней линейных форм”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2014, № 2, 9–14  mathnet  mathscinet; S. B. Gashkov, E. T. Shavgulidze, “Representation of monomials as a sum of powers of linear forms”, Moscow University Mathematics Bulletin, 69:2 (2014), 51–55  crossref
    13. К. Л. Рычков, “Достаточные условия локальной бесповторности минимальных $\pi$-схем, реализующих линейные булевы функции”, Дискретн. анализ и исслед. опер., 22:5 (2015), 71–85  mathnet  crossref  mathscinet  elib; K. L. Rychkov, “Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating”, J. Appl. Industr. Math., 9:4 (2015), 580–587  crossref
    14. И. С. Сергеев, “Верхние оценки сложности и глубины формул для MOD-функций”, Дискрет. матем., 28:2 (2016), 108–116  mathnet  crossref  mathscinet  elib; I. S. Sergeev, “Upper bounds for the size and the depth of formulae for MOD-functions”, Discrete Math. Appl., 27:1 (2017), 15–22  crossref  isi
    15. К. Л. Рычков, “О сложности реализации линейной булевой функции в классе $\pi$-схем”, Дискретн. анализ и исслед. опер., 25:3 (2018), 36–94  mathnet  crossref  elib; K. L. Rychkov, “Complexity of the realization of a linear Boolean function in the class of $\pi$-schemes”, J. Appl. Industr. Math., 12:3 (2018), 540–576  crossref
    16. К. Л. Рычков, “О совершенности минимальных правильных разбиений множества рёбер $n$-мерного куба”, Дискретн. анализ и исслед. опер., 26:4 (2019), 74–107  mathnet  crossref
    17. С. Б. Гашков, И. С. Сергеев, “О значении работ В. М. Храпченко”, ПДМ, 2020, № 48, 109–124  mathnet  crossref
  • Математические заметки Mathematical Notes
    Просмотров:
    Эта страница:201
    Полный текст:107
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020