?
Some Extension of Inversion Complexity of Boolean Functions
Cornell University
,
2015.
Научное направление:
Математика
Язык:
английский
Ключевые слова: circuit complexityBoolean circuit complexityBoolean function complexityinversion complexityMarkov's theoremсложность булевых функцийсложность схем из функциональных элементовинверсионная сложностьтеорема Маркова
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Кочергин В. В., Михайлович А. В., Прикладная дискретная математика 2015 № 4 С. 24-31
Исследуется сложность реализации булевых функций и систем булевых функций схемами в базисе, состоящем из элементов двух сортов. Элементами первого сорта являются произвольные монотонные функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго сорта, каждой такой функции приписан положительный вес. Для случая, когда отрицание является единственным элементом второго сорта, А. ...
Добавлено: 8 декабря 2015 г.
Mikhailovich A. V., Kochergin V. V., / Cornell University. Series math "arxiv.org". 2015.
Добавлено: 20 октября 2015 г.
Михайлович А. В., Кочергин В. В., XXI век: итоги прошлого и проблемы настоящего плюс 2017 № 4(38) С. 98-105
Рассматривается задача об экономной реализации булевых функций и функций многозначной логики схемами из функциональных элементов в бесконечном базисе, состоящем из всех монотонных и конечного числа немонотонных функций, причем мерой качества реализации является немонотонная сложность — число использований немонотонных элементов (монотонные функции «бесплатны»). Для случая реализации систем булевых функций в базисе, содержащем помимо монотонных функций только ...
Добавлено: 28 сентября 2017 г.
Kochergin Vadim V., Mikhailovich Anna V., Discrete Mathematics and Applications 2017 Vol. 27 No. 5 P. 295-302
The paper is concerned with the complexity of realization of 𝑘-valued logic functions by logic circuits over an infinite complete bases containing all monotone functions; the weight of monotone functions (the cost of use) is assumed to be 0. The complexity problem of realizations of Boolean functions over a basis having negation as the only ...
Добавлено: 14 марта 2018 г.
Mikhailovich A.V., Kochergin V.V., Siberian Electronic Mathematical Reports 2017 Vol. 14 P. 1100-1107
Добавлено: 28 сентября 2017 г.
Михайлович А. В., Кочергин В. В., Дискретная математика 2016 Т. 28 № 4 С. 80-90
Рассматривается задача о сложности реализации функций k-значной логики схемами в бесконечных полных базисах, содержащих все монотонные функции; вес монотонных функций (стоимость использования) считается равным 0. Для сложности реализации булевых функций в случае, когда единственным немонотонным элементом базиса является отрицание, исчерпывающее описание было получено А. А. Марковым. В 1957 году он установил, что минимальное число отрицаний, достаточное для ...
Добавлено: 25 февраля 2017 г.
Кочергин В. В., Михайлович А. В., Дискретный анализ и исследование операций 2018 Т. 25 № 1 С. 42-74
Исследуется сложность реализации функций k-значной логики (k > 2) схемами из функциональных элементов в бесконечном базисе, состоящем из отрицания Поста, т.е. функции x+1 (mod k), и всех монотонных функций. Под сложностью понимается общее число элементов в схеме. Для произвольной функии f установлены отличающиеся друг от друга не более чем на единицу нижняя и верхняя оценки ...
Добавлено: 28 сентября 2017 г.
V.V. Kochergin, A.V. Mikhailovich, Computational Mathematics and Modeling 2019 Vol. 30 No. 1 P. 13-25
Добавлено: 22 апреля 2019 г.
Михайлович А. В., Кочергин В. В., Математические заметки 2019 Т. 105 № 1 С. 32-41
Исследуется задача о сложности реализации булевых функций схемами в бесконечных полных базисах, содержащих все монотонные функции, имеющие при этом нулевой вес (стоимость использования) и конечное число немонотонных функций единичного веса. Для сложности реализации булевых функций в случае, когда единственным немонотонным элементом базиса является отрицание, исчерпывающее описание было получено А.А. Марковым: минимальное число отрицаний, достаточное для ...
Добавлено: 28 сентября 2017 г.
Кочергин В. В., Михайлович А. В., Mathematical notes 2023 Vol. 113 No. 5 P. 794-803
Добавлено: 19 ноября 2023 г.
Kochergin V.V., Mikhailovich A.V., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 1 P. 40-58
Добавлено: 11 марта 2018 г.
V.V. Kochergin, A.V. Mikhailovich, Mathematical notes 2019 Vol. 105 No. 1 P. 28-35
Добавлено: 22 апреля 2019 г.
Максимов Ю. В., Computational Mathematics and Mathematical Physics 2015 Vol. 49 No. 7 P. 1327
Добавлено: 30 октября 2015 г.
Михайлович А. В., Кочергин В. В., В кн. : Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.). : М. : Изд-во механико-математического факультета МГУ, 2016. С. 142-145.
Исследуются различные обобщения известных теорем А. А. Маркова об инверсионной сложности систем булевых функций. ...
Добавлено: 31 августа 2016 г.
Максимов Ю. В., Doklady Mathematics 2012 Vol. 86 No. 3 P. 854-856
Добавлено: 30 октября 2015 г.
Михайлович А. В., Кочергин В. В., В кн. : Материалы 5-й Российской школы-семинара "Синтаксис и семантика логических систем". : Улан-Удэ : Издательство Бурятского госуниверситета, 2017. С. 48-52.
Исследуется задача о сложности реализации систем функций k-значной логики схемами из функциональных элементов (логическими схемами) в базисах, состоящих из элементов двух сортов. Элементами первого сорта являются произвольные монотонные функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго сорта, каждой такой функции приписан единичный вес. ...
Добавлено: 22 сентября 2017 г.
In 1992, A. Hiltgen provided first constructions of provably (slightly) secure cryptographic primitives, namely feebly one-way functions. These functions are provably harder to invert than to compute, but the complexity (viewed as the circuit complexity over circuits with arbitrary binary gates) is amplified only by a constant factor (in Hiltgen’s works, the factor approaches 2). ...
Добавлено: 19 февраля 2013 г.
Беломестный Д. В., Иосипой Л. С., Mathematics and Computers in Simulation 2021 No. 181 P. 351-363
Добавлено: 31 октября 2020 г.
D. V. Gribanov, D.S. Malyshev, P. M. Pardalos и др., Journal of Combinatorial Optimization 2018 Vol. 35 No. 4 P. 1128-1146
Добавлено: 19 февраля 2018 г.
Ревенко А. В., Кузнецов С. О., Fundamenta Informaticae 2012 Vol. 4 No. 115 P. 377-394
Атрибутивное исследование свойств функций на множествах. ...
Добавлено: 31 декабря 2012 г.
Ясницкий Л. Н., Пермь : Пермский государственный национальный исследовательский университет. – Электронные данные. , 2020
В сборнике представлены материалы Международной конференции «Интеллектуальные системы в науке и технике» и Шестой всероссийской научно-практической конференции «Искусственный интеллект в решении актуальных социальных и экономических проблем ХХI века», которая проводилась 12–18 октября 2020 г. в г. Перми в рамках Пермского естественнонаучного форума «Математика и глобальные вызовы XXI века».
Сборник предназначен для научных и педагогических работников, преподавателей, аспирантов, магистрантов, студентов ...
Добавлено: 4 декабря 2020 г.
Беклемишев Л. Д., Оноприенко А. А., Математический сборник 2015 Т. 206 № 9 С. 3-20
Формулируются системы преобразований термов, число шагов работы которых на произвольном входе конечно, но не ограничивается никакой вычислимой функцией, доказуемо тотальной в арифметике Пеано PА. Тем самым, утверждение о сходимости таких систем не доказуемо в PA. Эти системы получаются из независимого комбинаторного утверждения, известного как принцип червя; их также можно рассматривать как вариант хорошо известной игры Геракла и гидры, ...
Добавлено: 13 марта 2016 г.
Малышев Д. С., Вестник Нижегородского университета им. Н.И. Лобачевского 2008 № 6 С. 141-146
Рассматривается понятие граничного класса, которое является полезным инструментом для анализа вычислительной сложности задач на графах. Исследуются два конкретных класса графов, и приводятся задачи, для которых эти классы являются граничными. ...
Добавлено: 31 августа 2012 г.