Войти
В математике и информатике, предикат BIT или кодирование Аккермана, иногда пишется BIT (i, j) - это предикат , который проверяет, равен ли j-й бит числа i 1, когда i записывается в двоичном формате.
Предикат BIT был впервые введен как кодирование натуральных чисел Вильгельмом Аккерманом в его статье 1937 года (Согласованность общей теории множеств).
Каждое натуральное число кодирует конечный набор, и каждый конечный набор представлен натуральным числом. В этом отображении используется двоичная система счисления . Если число n кодирует конечный набор A и i-я двоичная цифра n равна 1, то набор, кодируемый i, является элементом из A.
Кодирование Аккермана - примитивная рекурсивная функция.
В языках программирования, таких как C, C ++, Java или Python, которые предоставляют право оператор сдвига >>и побитовое логическое значение и оператор , предикат BIT BIT (i, j) может быть реализован выражением (i>>j) 1. Здесь биты i пронумерованы от младших битов к старшим битам в двоичном представлении i, при этом бит единиц пронумерован как бит 0.
В математическом исследовании компьютерной безопасности проблема поиска частной информации может быть смоделирована как проблема, в которой клиент, обменивающийся данными с набором серверов, хранящих двоичное число i, желает определить результат предиката BIT BIT (i, j) без разглашения значения j серверам. Чор и др. (1998) описывают метод репликации i на двух серверах таким образом, чтобы клиент мог решить проблему поиска частной информации, используя значительно меньший объем связи, чем было бы необходимо для восстановления полного значения i.
Предикат BIT часто исследуется в контексте логики первого порядка, где мы можем исследовать систему, полученную в результате добавления предиката BIT к логике первого порядка.. В описательной сложности класс сложности FO + BIT, полученный в результате добавления предиката BIT к FO, дает более устойчивый класс сложности. Класс FO + BIT логики первого порядка с предикатом BIT аналогичен классу FO + PLUS + TIMES логики первого порядка с предикатами сложения и умножения.
Граф Радо: например, существует ребро от 0 до 3, потому что 0-й бит 3 не равен нулю. Акерманн в 1937 году и Ричард Радо в 1964 году использовали этот предикат для построения бесконечный граф Rado. По своей конструкции вершины этого графа соответствуют неотрицательным целым числам, записанным в двоичном формате, и существует неориентированное ребро от вершины i к вершине j для i < j, when BIT(j,i) is nonzero.
