На семінарі кафедри Комп’ютерних систем, мереж і кібербезпеки Національного аерокосмічного університету ім. М.Є. Жуковського “ХАІ” 29.09.23 року була заслухана доповідь професора кафедри Електроніки і комп’ютерної техніки Сумського державного університету, д.т.н. Борисенка Олексія Андрійовича на тему: «Синтез завадостійких комбінаційних цифрових схем на несумісних булевих функціях». В цій доповіді проф. Борисенко О. А. доповів про відкритий ним новий клас булевих функцій, названий несумісними булевими функціями або Б-функціями, які з одного боку були завадостійкі, а з іншого були здійсненні за поліноміальний (реальний) час.
Задача здійсненності в загальній формі P = NP, і в першу чергу для будь-якої булевої функції, стоїть в математичній логікі з 1971 року і до цього часу не вирішена. Сьогодні інститутом Клея (Кємбрідж, Масачусетс, США) пропонується нагорода в мільйон доларів за вирішення кожної з них. В українській Вікіпедії говориться, що «питання полягає в тому, чи для всіх задач, для яких комп’ютер може швидко перевірити заданий алгоритм (тобто, протягом поліноміального часу), він також може швидко знайти цей розв’язок. Проблема рівності класів складності P і NP є однією з найважливіших проблем теорії алгоритмів і має багато далекосяжних наслідків у математиці, філософії й криптографії (див. Наслідки рівності класів P і NP).» Офіційна постановка задачі належить Стівену Куку.
Для двох окремих невеликих класів булевих функцій 1-здійсненних і 2-здійсненних раніше було доведено, що вони поліноміально здійсненні. Тепер після новітньої роботи проф. Борисенка О. А. з’явився клас Б-функцій, в який входить більше половини всіх можливих логічних функцій, які поліноміально здійсненні. Всі інші булеві функції відносяться до сумісних функцій, про багато з яких поки що неможливо сказати ні що вони здійсненні, ні що вони нездійсненні. Тобто задача тисячоліття значно звузилась, і тепер вона має іншу постанову в вигляді доведення можливості чи неможливості поліноміального переходу від сумісних функцій до Б-функцій. Крім вказаної важливої властивості здійсненності, Б-функції також дозволяють будувати завадостійкі і відмово стійкі комбінаційні схеми, що має значення для побудови цифрової апаратури з підвищеною надійністю роботи.
Синтез Б-функцій проводиться за відомими алгоритмами для сумісних булевих функцій, але має свою специфіку, яка виходить з великої їх інформаційної насиченості. Доповідач вказав на літературу, де можна знайти матеріал, який відноситься до Б-функцій, серед якої була написана ним в 2020 році монографія «Комп’ютерна логіка», на основі якої за вибором більше 50 студентів він викладав однойменну дисципліну «Комп’ютерна логіка». Доповідь була уважно заслухана 120 учасниками семінару і обговорена ними. На даний час по цій доповіді готується велика стаття в відповідний журнал високого рангу.
Подивитись відео з виступом проф. Борисенка О. А. на семінарі в ХАІ 29 09 23 на тему «Синтез завадостійких комбінаційних цифрових схем на несумісних булевих функціях». можна за адресою:
https://www.youtube.com/watch?v=HpaqBKwq57Y
At the Department of Computer Systems, Networks and Cyber Security seminar of the National Aerospace University named after M.E. Zhukovsky “KHAI” on September 29, 2023, the professor of the Department of Electronics and Computer Technics of Sumy State University, Ph.D. Oleksiy Andriyovych Borysenko on the topic: «Synthesis of interference-resistant combinational digital circuits on incompatible Boolean functions». In this report, Prof. O.A. Borysenko reported on a new class of Boolean functions that he discovered, called incompatible Boolean functions or B-functions, which were, on the one hand, resistant to interference and, on the other hand, were feasible in polynomial (real) time.
The feasibility problem in the general form P = NP, and primarily for any Boolean function, has been in mathematical logic since 1971 and has not been solved until now. Today, the Clay Institute (Cambridge, Massachusetts, USA) is offering a million-dollar reward for solving each of them. Ukrainian Wikipedia says that “the question is whether, for all problems for which a computer can quickly check a given algorithm (i.e., within polynomial time), it can also quickly find this solution. The problem of the equality of the complexity classes P and NP is one of the most important problems in the theory of algorithms and has many far-reaching consequences in mathematics, philosophy, and cryptography (see Consequences of the equality of the classes P and NP).» The official statement of the problem belongs to Stephen Cook.
For two separate small classes of Boolean functions, 1-realizable and 2-realizable, it was previously proved that they are polynomially feasible. Now, after the latest work of Prof. O. A. Borysenko, a class of B-functions appeared, which includes more than half of all possible logical functions that are polynomially feasible. All other Boolean functions belong to compatible functions, many of which it is still impossible to say either that they are feasible or that they are not feasible. That is, the millennium task has narrowed considerably. Now, it has a different resolution, proving the possibility or impossibility of a polynomial transition from compatible functions to B-functions. In addition to the specified important property of feasibility, B-functions also allow building interference-resistant and fault-resistant combinational circuits, which is important for the construction of digital equipment with increased reliability of operation.
The synthesis of B-functions is carried out according to well-known algorithms for compatible Boolean functions, but it has its own specificity, which comes from its large information saturation. The speaker pointed to the literature where you can find material related to B-functions, among which was the monograph “Computer Logic” written by him in 2020, based on which he taught the discipline of the same name “Computer Logic” to the choice of more than 50 students. The report was carefully listened to by 120 seminar participants and discussed by them. Currently, a large article is being prepared for this report in a corresponding high-ranking journal.
Watch the video with the speech of Prof. O. A. Borysenko at the seminar in «KHAI» 29.09.23 on the topic «Synthesis of interference-resistant combinational digital circuits on incompatible Boolean functions» available at:
