BIT-предикат

Проверка указанного бита в двоичном числе

В математике и информатике предикат BIT , иногда записываемый как , ${\displaystyle {\text{BIT}}(i,j)}$ является предикатом , который проверяет, равен ли th бит числа (начиная с младшей значащей цифры ) 1, когда записан как двоичное число . Его математические приложения включают моделирование отношения принадлежности наследственно конечных множеств и определение отношения смежности графа Радо . В информатике он используется для эффективного представления структур данных множеств с использованием битовых векторов , при определении проблемы поиска частной информации из коммуникационной сложности и в дескриптивной теории сложности для формулирования логических описаний классов сложности . ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle i}$

История

Предикат BIT был впервые введен в 1937 году Вильгельмом Аккерманом для определения кодировки Аккермана , которая кодирует наследственно конечные множества как натуральные числа . ^{[1] [2]} Предикат BIT может использоваться для выполнения тестов на принадлежность для закодированных множеств: является истинным тогда и только тогда, когда множество, закодированное , является членом множества, закодированного . [ ^1] ${\displaystyle {\text{BIT}}(i,j)}$ ${\displaystyle j}$ ${\displaystyle i}$

Аккерман обозначил предикат как , используя шрифт Fraktur , чтобы отличить его от обозначения , которое он использовал для членства во множестве (сокращение от « является элементом » на немецком языке). ^[1] Обозначение и название «предикат BIT » пришли из работы Рональда Фейгина и Нила Иммермана , которые применили этот предикат в теории вычислительной сложности как способ кодирования и декодирования информации в конце 1980-х и начале 1990-х годов. ^[a] ${\displaystyle {\text{BIT}}(i,j)}$ ${\displaystyle {\mathfrak {El}}(j,i)}$ ${\displaystyle \mathrm {El} (j,i)}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle {\text{BIT}}(i,j)}$

Описание и реализация

Двоичное представление числа — это выражение для в виде суммы различных степеней двойки , где каждый бит в этом выражении равен либо 0, либо 1. Обычно его записывают в двоичной нотации как просто последовательность этих битов, . Учитывая это расширение для , предикат BIT определяется как равный . Его можно вычислить по формуле , где — функция пола , а mod — функция по модулю . ^[6] Предикат BIT — это примитивная рекурсивная функция . ^{[2] [7]} Как бинарное отношение (производящее истинные и ложные значения, а не 1 и 0 соответственно), предикат BIT асимметричен : не существует двух чисел и , для которых оба и являются истинными. ^[b] ${\displaystyle i}$ ${\displaystyle i}$ $${\displaystyle i=\cdots b_{3}2^{3}+b_{2}2^{2}+b_{1}2^{1}+b_{0}2^{0}}$$ ${\displaystyle b_{j}}$ ${\displaystyle \cdots b_{3}b_{2}b_{1}b_{0}}$ ${\displaystyle i}$ ${\displaystyle {\text{BIT}}(i,j)}$ ${\displaystyle b_{j}}$ $${\displaystyle {\text{BIT}}(i,j)=\left\lfloor {\frac {i}{2^{j}}}\right\rfloor {\bmod {2}},}$$ ${\displaystyle \lfloor \cdot \rfloor }$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle {\text{BIT}}(i,j)}$ ${\displaystyle {\text{BIT}}(j,i)}$

В таких языках программирования, как C , C++ , Java или Python , которые предоставляют оператор сдвига вправо >> и побитовый логический оператор & и , предикат BIT может быть реализован выражением . Подвыражение сдвигает биты в двоичном представлении так, что бит сдвигается в позицию 0, а подвыражение маскирует оставшиеся биты, оставляя только бит в позиции 0. Как и в формуле модульной арифметики выше, значение выражения равно 1 или 0, соответственно, поскольку значение является истинным или ложным. ^[9] ${\displaystyle {\text{BIT}}(i,j)}$(i>>j)&1i>>j ${\displaystyle i}$ ${\displaystyle b_{j}}$&1 ${\displaystyle {\text{BIT}}(i,j)}$

Приложения

Установить структуры данных

Для набора, представленного как битовый массив , предикат BIT может использоваться для проверки принадлежности к набору. Например, подмножества неотрицательных целых чисел могут быть представлены битовым массивом с единицей в позиции , когда является членом подмножества, и нулем в этой позиции, когда он не является членом. Когда такой битовый массив интерпретируется как двоичное число, набор для distinct представляется как двоичное число . Если является набором, представленным таким образом, и является числом, которое может быть или не быть элементом , то возвращает ненулевое значение, когда является членом, и ноль, когда он им не является. ^[c] ${\displaystyle \{0,1,\ldots \}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle \{i,j,k,\dots \}}$ ${\displaystyle i,j,k,\dots }$ ${\displaystyle 2^{i}+2^{j}+2^{k}+\cdots }$ ${\displaystyle S}$ ${\displaystyle i}$ ${\displaystyle S}$ ${\displaystyle {\text{BIT}}(S,i)}$ ${\displaystyle i}$

Тот же метод может быть использован для проверки членства в подмножествах любой последовательности различных значений, закодированных с использованием степеней двойки, экспоненты которых являются позициями элементов в этой последовательности, а не их значениями. Например, в фреймворке коллекций Java этот метод используется для реализации структуры данных набора для перечислимых типов . ^[11] Кодирование наследственно конечных множеств Аккермана является примером этого метода для рекурсивно сгенерированной последовательности наследственно конечных множеств. ^[d] ${\displaystyle x_{0},x_{1},\dots }$java.util.EnumSet

Поиск частной информации

В математическом исследовании компьютерной безопасности проблема поиска частной информации может быть смоделирована как та, в которой клиент, взаимодействующий с набором серверов, которые хранят двоичное число , ${\displaystyle i}$ желает определить результат предиката BIT, не разглашая значение серверам . Чор и др. (1998) описывают метод репликации между двумя серверами таким образом, что клиент может решить проблему поиска частной информации, используя существенно меньший объем коммуникации, чем это было бы необходимо для восстановления полного значения . [ ^13] ${\displaystyle {\text{BIT}}(i,j)}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle i}$

Сложность и логика

Предикат BIT часто рассматривается в контексте логики первого порядка , где системы логики возникают в результате добавления предиката BIT к логике первого порядка. В описательной сложности класс сложности FO описывает класс формальных языков , которые могут быть описаны формулой в логике первого порядка с операцией сравнения на полностью упорядоченных переменных (интерпретируемых как индексы символов в строке ) и с предикатами, которые проверяют, содержит ли эта строка заданный символ в заданном числовом индексе. Формула в этой логике определяет язык, состоящий из его конечных моделей . ^[e] Однако с помощью этих операций можно описать только очень ограниченный класс языков, регулярные языки без звезд . ^[15] Добавление предиката BIT к репертуару операций, используемых в этих логических формулах, приводит к более надежному классу сложности, FO[BIT] , что означает, что он менее чувствителен к незначительным изменениям в его определении. ^[f]

Класс FO[BIT] совпадает с классом FO[+,×] , логики первого порядка с предикатами сложения и умножения. ^[14] Он также совпадает с классом сложности схемы DLOGTIME - однородный AC 0 . Здесь AC ⁰ описывает задачи, которые могут быть вычислены схемами вентилей И и вентилей ИЛИ с полиномиальным размером, ограниченной высотой и неограниченным разветвлением. «Однородный» означает, что схемы всех размеров задач должны быть описаны одним алгоритмом. Более конкретно, должна быть возможность индексировать вентили каждой схемы числами таким образом, чтобы тип каждого вентиля и смежность между любыми двумя вентилями могли быть вычислены детерминированным алгоритмом, время которого логарифмически зависит от размера схемы (DLOGTIME). ^{[6] [16]}

Построение графика Радо

Граф Радо, построенный из предиката BIT. Например, ребро соединяет 0 с 3, поскольку 0-й бит 3 не равен нулю.

В 1964 году немецко-британский математик Ричард Радо использовал предикат BIT для построения бесконечного графа Радо . Конструкция Радо является просто симметризацией конструкции наследственных конечных множеств Аккермана 1937 года из предиката BIT: две вершины пронумерованы и являются смежными в графе Радо, когда либо или не равно нулю. ^[17] ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle {\text{BIT}}(i,j)}$ ${\displaystyle {\text{BIT}}(j,i)}$

Полученный граф обладает многими важными свойствами: он содержит каждый конечный неориентированный граф как индуцированный подграф , и любой изоморфизм его индуцированных подграфов может быть расширен до симметрии всего графа. ^[8]

Примечания

1. Раннее использование названия предиката BIT принадлежит Иммерману (1989). ^[3] В статье 1990 года Дэвид Микс Баррингтон приписывает нотацию и ее применение в дескриптивной сложности Фейгину; Баррингтон отдает должное Фейгину за вдохновение Иммермана на работу в этой области. ^[4] Однако, Аджтай и Фейгин (1990) ссылаются на « соотношение BIT Иммермана ». ^[5] ${\displaystyle {\text{BIT}}(i,j)}$
2. Об асимметрии отношения принадлежности множеству, которое кодирует предикат BIT, см. Кэмерон (2001). ^[8]
3. Арндт (2011). Арндт реализует предикат BIT с помощью , S&(1<<i)а не (S>>i)&1, но результат равен нулю или ненулю в равной степени для обеих реализаций. ^[10]
4. Тарау (2010). Реализация теста членства Тарау (как inSetв разделе «Вывод операций над множествами») сводится к проверке того, является ли , S&(1<<i) == 1<<iа не (S>>i)&1, аналогично тому, как это было у Арндта (2011). ^[12]
5. В некоторых источниках этот класс обозначается как FO[<] , чтобы указать на операцию сравнения; однако при определении классов сложности из логики таким образом операция сравнения не может быть опущена, ^[14] поэтому нет необходимости указывать на ее наличие.
6. Иммерман (1999), стр. 13: «Добавление BIT ... делает набор определяемых булевых запросов первого порядка более надежным классом сложности».

Ссылки

1. Аккерманн, Вильгельм (1937). «Die Widerspruchsfreiheit der allgemeinen Mengenlehre». Mathematische Annalen (на немецком языке). 114 : 305–315. дои : 10.1007/bf01594179. S2CID  120576556 . Проверено 9 января 2012 г.
2. Kirby, Laurence (2009). «Теория конечных множеств». Notre Dame Journal of Formal Logic . 50 (3): 227–244. doi : 10.1215/00294527-2009-009 .
3. Иммерман, Нил (1989). «Выразимость и параллельная сложность». Журнал SIAM по вычислениям . 18 (3): 625–638. doi :10.1137/0218043. MR  0996841.
4. Микс Баррингтон, Дэвид А. (1990). «Расширения идеи Макнотона». Математическая теория систем . 23 (3): 147–164. doi :10.1007/BF02090772. MR  1062347. S2CID  198177167.
5. Ajtai, Miklós ; Fagin, Ronald (1990). «Достижимость сложнее для направленных, чем для ненаправленных конечных графов». Журнал символической логики . 55 (1): 113–150. doi :10.2307/2274958. JSTOR  2274958. MR  1043548. S2CID  14177866.
6. Lindell, Steven (1992). "Чисто логическая характеристика однородности схем" (PDF) . Труды Седьмой ежегодной конференции по теории структур в теории сложности, Бостон, Массачусетс, США, 22-25 июня 1992 г. . IEEE Computer Society. стр. 185–192. doi :10.1109/SCT.1992.215393. Архивировано из оригинала 2017-08-30 . Получено 2023-07-04 .{{cite conference}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка )
7. Раутенберг, Вольфганг (2010). Краткое введение в математическую логику (3-е изд.). Нью-Йорк : Springer Science+Business Media . стр. 261. doi :10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6.
8. Cameron, Peter J. (2001). "The random graph revisited" (PDF) . European Congress of Mathematics , Vol. I (Barcelona, ​​2000) . Progr. Math. Vol. 201. Basel: Birkhäuser. pp. 267–274. doi :10.1007/978-3-0348-8268-2_15. MR  1905324.
9. Venugopal, KR (1997). Мастерство C++. Tata McGraw-Hill Publishing Company. стр. 123. ISBN 9780074634547..
10. Арндт, Йорг (2011). "1.9.2: Проверка наличия элемента в заданном наборе". Matters Computational: Ideas, Algorithms, Source Code (PDF) . Springer. стр. 24.
11. Блох, Джошуа (2008). «Пункт 32: Используйте enumSet вместо битовых полей». Effective Java (2-е изд.). Addison-Wesley Professional. стр. 159–160. ISBN 9780132778046.
12. Tarau, Paul (2010). «Унифицированное формальное описание арифметических и теоретико-множественных типов данных». В Autexier, Serge; Calmet, Jacques; Delahaye, David; Ion, Patrick DF; Rideau, Laurence; Rioboo, Renaud; Sexton, Alan P. (ред.). Intelligent Computer Mathematics, 10-я международная конференция, AISC 2010, 17-й симпозиум, Calculemus 2010 и 9-я международная конференция, MKM 2010, Париж, Франция, 5–10 июля 2010 г., Труды . Заметки лекций по информатике. Том 6167. Springer. стр. 247–261. arXiv : 1006.5768 . doi :10.1007/978-3-642-14128-7_21.
13. Чор, Бенни ; Кушилевиц, Эяль; Гольдрейх, Одед ; Судан, Мадху (1998). «Поиск частной информации». Журнал АКМ . 45 (6): 965–981. дои : 10.1145/293347.293350 . S2CID  544823..
14. Immerman, Neil (1999). Описательная сложность . Нью-Йорк: Springer-Verlag. С. 13–16. ISBN 0-387-98600-6.
15. Перрен, Доминик ; Пин, Жан-Эрик (1986). «Логика первого порядка и множества, свободные от звезд». Журнал компьютерных и системных наук . 32 (3): 393–406. doi : 10.1016/0022-0000(86)90037-1 . MR  0858236.
16. Mix Barrington, David A.; Immerman, Neil ; Straubing, Howard (1990). «О единообразии в пределах NC ¹ ». Журнал компьютерных и системных наук . 41 (3): 274–306. doi :10.1016/0022-0000(90)90022-D. MR  1079468.
17. Радо, Ричард (1964). «Универсальные графы и универсальные функции» (PDF) . Акта Арит . 9 (4): 331–340. дои : 10.4064/aa-9-4-331-340 ..