Predicado BIT

En matemáticas y ciencias de la computación , el predicado BIT , a veces escrito como ,${\displaystyle {\text{BIT}}(i,j)}$ es un predicado que prueba si el bit n.º del número (empezando por el dígito menos significativo ) es 1, cuando se escribe como un número binario . Sus aplicaciones matemáticas incluyen el modelado de la relación de pertenencia de conjuntos finitos hereditarios y la definición de la relación de adyacencia del grafo de Rado . En ciencias de la computación, se utiliza para representaciones eficientes de estructuras de datos de conjuntos utilizando vectores de bits , en la definición del problema de recuperación de información privada a partir de la complejidad de la comunicación y en la teoría de la complejidad descriptiva para formular descripciones lógicas de clases de complejidad . ${\estilo de visualización j}$ ${\estilo de visualización i}$${\estilo de visualización i}$

El predicado BIT fue introducido por primera vez en 1937 por Wilhelm Ackermann para definir la codificación de Ackermann , que codifica conjuntos finitos hereditarios como números naturales . ^{[1] [2]} El predicado BIT se puede utilizar para realizar pruebas de pertenencia para los conjuntos codificados: es verdadero si y solo si el conjunto codificado por es un miembro del conjunto codificado por . ^[1]${\displaystyle {\text{BIT}}(i,j)}$${\estilo de visualización j}$${\estilo de visualización i}$

Ackermann denotó el predicado como , usando una fuente Fraktur para distinguirlo de la notación que usó para la pertenencia a un conjunto (abreviatura de " es un elemento de " en alemán). ^[1] La notación , y el nombre "el predicado BIT", provienen del trabajo de Ronald Fagin y Neil Immerman , quienes aplicaron este predicado en la teoría de la complejidad computacional como una forma de codificar y decodificar información a fines de la década de 1980 y principios de la de 1990. ^[a]${\displaystyle {\text{BIT}}(i,j)}$ ${\displaystyle {\mathfrak {El}}(j,i)}$${\displaystyle \mathrm {El} (j,i)}$${\estilo de visualización j}$${\estilo de visualización i}$${\displaystyle {\text{BIT}}(i,j)}$

La representación binaria de un número es una expresión para como una suma de potencias distintas de dos , donde cada bit en esta expresión es 0 o 1. Se escribe comúnmente en notación binaria como simplemente la secuencia de estos bits, . Dada esta expansión para , el predicado BIT se define como igual a . Se puede calcular a partir de la fórmula donde es la función base y mod es la función módulo . ^[6] El predicado BIT es una función recursiva primitiva . ^{[2] [7]} Como una relación binaria (que produce valores verdaderos y falsos en lugar de 1 y 0 respectivamente), el predicado BIT es asimétrico : no existen dos números y para los cuales tanto y sean verdaderos. ^[b]${\estilo de visualización i}$${\estilo de visualización i}$$${\displaystyle i=\cdots b_{3}2^{3}+b_{2}2^{2}+b_{1}2^{1}+b_{0}2^{0}}$$ $Estilo de visualización b_ {j}}$$Estilo de visualización: b_{3}b_{2}b_{1}b_{0}$${\estilo de visualización i}$${\displaystyle {\text{BIT}}(i,j)}$$Estilo de visualización b_ {j}}$$${\displaystyle {\text{BIT}}(i,j)=\left\lfloor {\frac {i}{2^{j}}}\right\rfloor {\bmod {2}},}$$${\displaystyle \lfloor \cdot \rfloor}$${\estilo de visualización i}$${\estilo de visualización j}$${\displaystyle {\text{BIT}}(i,j)}$${\displaystyle {\text{BIT}}(j,i)}$

En lenguajes de programación como C , C++ , Java o Python que proporcionan un operador de desplazamiento a la derecha >> y un operador booleano y bit & a bit , el predicado BIT se puede implementar mediante la expresión . La subexpresión desplaza los bits en la representación binaria de de modo que el bit se desplaza a la posición 0, y la subexpresión enmascara los bits restantes, dejando solo el bit en la posición 0. Al igual que con la fórmula aritmética modular anterior, el valor de la expresión es 1 o 0, respectivamente, ya que el valor de es verdadero o falso. ^[9]${\displaystyle {\text{BIT}}(i,j)}$(i>>j)&1i>>j${\estilo de visualización i}$$Estilo de visualización b_ {j}}$&1 ${\displaystyle {\text{BIT}}(i,j)}$

Para un conjunto representado como una matriz de bits , el predicado BIT se puede utilizar para probar la pertenencia al conjunto. Por ejemplo, los subconjuntos de los números enteros no negativos se pueden representar mediante una matriz de bits con un uno en la posición cuando es un miembro del subconjunto y un cero en esa posición cuando no es un miembro. Cuando dicha matriz de bits se interpreta como un número binario, el conjunto para distinct se representa como el número binario . Si es un conjunto, representado de esta manera, y es un número que puede o no ser un elemento de , entonces devuelve un valor distinto de cero cuando es un miembro y cero cuando no lo es. ^[c]${\displaystyle \{0,1,\lpuntos \}}$${\estilo de visualización i}$${\estilo de visualización i}$${\displaystyle \{i,j,k,\puntos \}}$${\displaystyle i,j,k,\puntos}$${\displaystyle 2^{i}+2^{j}+2^{k}+\cpuntos}$${\estilo de visualización S}$${\estilo de visualización i}$${\estilo de visualización S}$${\displaystyle {\text{BIT}}(S,i)}$${\estilo de visualización i}$

La misma técnica puede utilizarse para probar la pertenencia a subconjuntos de cualquier secuencia de valores distintos, codificada utilizando potencias de dos cuyos exponentes son las posiciones de los elementos en esta secuencia, en lugar de sus valores. Por ejemplo, en el marco de colecciones de Java , se utiliza esta técnica para implementar una estructura de datos de conjunto para tipos enumerados . ^[11] La codificación de Ackermann de los conjuntos finitos hereditarios es un ejemplo de esta técnica, para la secuencia generada recursivamente de conjuntos finitos hereditarios. ^[d]${\displaystyle x_{0},x_{1},\puntos}$java.util.EnumSet

En el estudio matemático de la seguridad informática , el problema de recuperación de información privada se puede modelar como uno en el que un cliente, que se comunica con una colección de servidores que almacenan un número binario ,${\estilo de visualización i}$ desea determinar el resultado de un predicado BIT sin divulgar el valor de a los servidores. Chor et al. (1998) describen un método para replicar entre dos servidores de tal manera que el cliente puede resolver el problema de recuperación de información privada utilizando una cantidad sustancialmente menor de comunicación de la que sería necesaria para recuperar el valor completo de . ^[13]${\displaystyle {\text{BIT}}(i,j)}$${\estilo de visualización j}$${\estilo de visualización i}$${\estilo de visualización i}$

El predicado BIT se examina a menudo en el contexto de la lógica de primer orden , donde los sistemas de lógica resultan de añadir el predicado BIT a la lógica de primer orden. En la complejidad descriptiva , la clase de complejidad FO describe la clase de lenguajes formales que se pueden describir mediante una fórmula en lógica de primer orden con una operación de comparación sobre variables totalmente ordenadas (interpretadas como los índices de caracteres en una cadena ) y con predicados que prueban si esta cadena tiene un carácter dado en un índice numérico dado. Una fórmula en esta lógica define un lenguaje que consiste en sus modelos finitos . ^[e] Sin embargo, con estas operaciones, solo se puede describir una clase muy restringida de lenguajes, los lenguajes regulares sin estrellas . ^[15] Añadir el predicado BIT al repertorio de operaciones utilizadas en estas fórmulas lógicas da como resultado una clase de complejidad más robusta, FO[BIT] , lo que significa que es menos sensible a variaciones menores en su definición. ^[f]

La clase FO[BIT] es la misma que la clase FO[+,×] , de lógica de primer orden con predicados de adición y multiplicación. ^[14] También es la misma que la clase de complejidad de circuito DLOGTIME - uniforme AC ⁰ . Aquí, AC ⁰ describe los problemas que pueden ser calculados por circuitos de puertas AND y puertas OR con tamaño polinomial, altura acotada y abanico de salida ilimitado. "Uniforme" significa que los circuitos de todos los tamaños de problemas deben ser descritos por un único algoritmo. Más específicamente, debe ser posible indexar las puertas de cada circuito por números de tal manera que el tipo de cada puerta y la adyacencia entre dos puertas cualesquiera puedan ser calculadas por un algoritmo determinista cuyo tiempo sea logarítmico en el tamaño del circuito (DLOGTIME). ^{[6] [16]}

En 1964, el matemático germano-británico Richard Rado utilizó el predicado BIT para construir el grafo infinito de Rado . La construcción de Rado es simplemente la simetrización de la construcción de Ackermann de 1937 de los conjuntos finitos hereditarios a partir del predicado BIT: dos vértices numerados y son adyacentes en el grafo de Rado cuando o es distinto de cero. ^[17]${\estilo de visualización i}$${\estilo de visualización j}$${\displaystyle {\text{BIT}}(i,j)}$${\displaystyle {\text{BIT}}(j,i)}$

El gráfico resultante tiene muchas propiedades importantes: contiene cada gráfico finito no dirigido como un subgráfico inducido , y cualquier isomorfismo de sus subgráficos inducidos puede extenderse a una simetría de todo el gráfico. ^[8]