• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Нижняя оценка немонотонной сложности функций многозначной логики
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
May 22, 2026
HSE Graduates AI Project Wins at TECH & AI Awards
Daria Davydova, graduate of the HSE Graduate School of Business and Head of the AI Implementation Unit at the Artificial Intelligence Department of Alfa-Bank, received a prize at the TECH & AI Awards. She was awarded for the best AI solution for optimising business processes. The winners were determined as part of the VII Russian Summit and Awards on Digital Transformation (CDO/CDTO Summit & Awards).
May 20, 2026
HSE University Opens First Representative Office of Satellite Laboratory in Brazil
HSE University-St Petersburg opened a representative office of the Satellite Laboratory on Social Entrepreneurship at the University of Campinas in Brazil. The platform is going to unite research and educational projects in the spheres of sustainable development, communications and social innovations.
May 18, 2026
The 'Second Shift' Is Not Why Women Avoid News
Women are more likely than men to avoid political and economic news, but the reasons for this behaviour are linked less to structural inequality or family-related stress than to personal attitudes and the emotional perception of news content. This conclusion was reached by HSE researchers after analysing data from a large-scale survey of more than 10,000 residents across 61 regions of Russia. The study findings have been published in Woman in Russian Society.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Нижняя оценка немонотонной сложности функций многозначной логики

С. 76–79.
Kochergin V., Mikhailovich A.
Language: Russian
Keywords: функции многозначной логикиmulti-valued logic functionsсхемная сложностьnonmonotone complexityнемонотонная сложность circuit complexitylower bound of complexityнижняя оценка сложности

In book

Материалы XIV Международного семинара "Дискретная математика и ее приложения" имени академика О.Б.Лупанова (Москва, МГУ, 20-25 июня 2022 г.)
М.: Институт прикладной математики им. М.В. Келдыша РАН, 2022.
Similar publications
The Exact Circuit Complexity of Boolean Functions in an Infinite Basis
V. V. Kochergin, A. V. Mikhailovich, Mathematical notes 2025 Vol. 117 No. 4 P. 579–594
The exact value of the complexity of the circuit implementation of an arbitrary Boolean function in a certain basis consisting of negation and all monotone Boolean functions is found. The complexity of a function is defined as the least number of basis elements sufficient to construct a circuit implementation of this function. ...
Added: February 28, 2026
Точное значение схемной сложности булевых функций в одном бесконечном базисе
Kochergin V., Mikhailovich A., Математические заметки 2025 Т. 117 № 4 С. 523–542
The exact value of the complexity of the circuit implementation of an arbitrary Boolean function in a certain basis consisting of negation and all monotone Boolean functions is found. The complexity of a function is defined as the least number of basis elements sufficient to construct a circuit implementation of this function. ...
Added: April 8, 2025
Математические вопросы кибернетики. Вып. 22
Mikhailovich A., Kochergin V., М.: Физматлит, 2024.
Added: March 10, 2025
Improvement of Nonmonotone Complexity Estimates of k-Valued Logic Functions
Kochergin V., Mikhailovich A., Mathematical notes 2023 Vol. 113 No. 5 P. 794–803
The problem of determining the nonmonotone complexity of the implementation ofk-valued logic functions by logic circuits in bases consisting of all monotone (with respect to thestandard order) functions and finitely many nonmonotone functions is investigated. In calculatingthe complexity measure under examination only those elements of the circuit which are assignednonmonotone basis functions are taken into ...
Added: November 19, 2023
Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games
Ignatiev A., Mihajlin I., Smal A., , in: 33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs, Volume 248.: Saarbrücken, Вадерн: Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022. Ch. 66.
Added: November 9, 2023
Сравнение оценок сложности для задач Р. Беллмана и О. Б. Лупанова
Kochergin V., В кн.: Материалы XIV Международного семинара "Дискретная математика и ее приложения" имени академика О.Б.Лупанова (Москва, МГУ, 20-25 июня 2022 г.).: М.: Институт прикладной математики им. М.В. Келдыша РАН, 2022. С. 4–16.
Задача Беллмана является обобщением классической задачи об эффективном возведении в степень, т.\,е. задачи о нахождении величины $l(x^n)$ --- минимального числа операций умножения, достаточного для вычисления по переменной $x$ величины $x^n$, при этом вычислительная модель допускает возможность многократного использования результатов промежуточных вычислений. Задача Лупанова заключается в нахождении сложности вычисления элемента конечной абелевой группы по ее образующим. Значение ...
Added: October 29, 2022
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit