предикат BIT

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

История

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

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

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

Двоичное представление числа $i$ является выражением для $i$ как сумма различных степеней двойки ,

$$i=\cdots b_{3}2^{3}+b_{2}2^{2}+b_{1}2^{1}+b_{0}2^{0}$$

где каждый бит $b_{j}$ в этом выражении равно либо 0, либо 1. Обычно его записывают в двоичной записи как просто последовательность этих битов: $\cdots b_{3}b_{2}b_{1}b_{0}$. Учитывая это расширение для $i$, предикат BIT ${\text{BIT}}(i,j)$ определяется как равный $b_{j}$. Его можно рассчитать по формуле

$${\text{BIT}}(i,j)=\left\lfloor {\frac {i}{2^{j}}}\right\rfloor {\bmod {2}},$$

где $\lfloor \cdot \rfloor$ — это функция пола , а mod — функция по модулю . Предикат BIT — это примитивно-рекурсивная функция . Как бинарное отношение (производящее истинные и ложные значения, а не 1 и 0 соответственно), предикат BIT асимметричен : не существует двух чисел. $i$ и $j$ для чего оба ${\text{BIT}}(i,j)$ и ${\text{BIT}}(j,i)$ верны.

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

Приложения

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

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

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

Получение частной информации

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

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

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

Класс FO[BIT] аналогичен классу FO[+,×] логики первого порядка с предикатами сложения и умножения. Он также аналогичен сложности схемы классу DLOGTIME — однородный переменный ток. ⁰ . Здесь, АС ⁰ описывает проблемы, которые могут быть решены с помощью схем логических элементов И и ИЛИ с полиномиальным размером, ограниченной высотой и неограниченным ответвлением. «Единый» означает, что схемы всех размеров задач должны описываться одним алгоритмом. Более конкретно, должна быть возможность индексировать элементы каждой схемы по номерам таким образом, чтобы тип каждого элемента и смежность между любыми двумя элементами можно было вычислить с помощью детерминированного алгоритма, время которого логарифмировано размером схемы. (ДЛОГТАЙМ).

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

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

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

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