Prime Factorization in Models of PV$_1$

Resumo Técnico: Fatoração de Números Primos em Modelos de PV1

1. Problema e Contexto

O artigo investiga os limites da Aritmética Limitada (Bounded Arithmetic), especificamente a teoria PV1 (uma extensão de primeira ordem da teoria PV de Cook, que corresponde a predicados de tempo polinomial).

O problema central é determinar se a teoria PV1 (mesmo quando estendida pelo esquema de escolha fortemente limitada, $BB(\Sigma^b_0)$) é capaz de provar que todo número inteiro maior ou igual a 2 possui um divisor primo.

• Em teorias mais fortes, como $S^1_2$, essa propriedade é provável através do princípio de maximização ($\Sigma^b_1$-LMAX), que permite encontrar o maior $k$ tal que um número é produto de $k$ inteiros $>1$.
• No entanto, a teoria PV1 não possui esse princípio de maximização (a menos que $NP \subseteq P/poly$).
• O objetivo do autor é mostrar que, sob uma hipótese de complexidade computacional padrão, a teoria PV1 não consegue provar a existência de fatoração prima para todos os números. Isso implica a existência de modelos não padrão de PV1 onde existem números que não possuem fatoração prima.

2. Hipótese de Trabalho

O resultado condicional baseia-se na dureza média da fatoração contra adversários de tempo polinomial não uniformes.

• Hipótese: Não existe uma família de circuitos booleanos de tamanho polinomial que possa fatorar uma fração constante de todos os produtos de dois primos de $n$ bits, para qualquer $n$.
• Esta é uma suposição criptográfica bem estabelecida (dureza média da fatoração).

3. Metodologia

O autor utiliza uma combinação de Teoremas de Testemunho (Witnessing Theorems) e Protocolos Estudante-Professor para estabelecer a inprovabilidade.

• Teorema de Testemunho KPT (Krajíček, Pudlák, Takeuti):

  • Este teorema afirma que se uma teoria como PV1 prova uma sentença da forma $\forall x \exists y \forall z \phi(x,y,z)$, então existe um algoritmo de tempo polinomial (o "estudante") que, interagindo com um "professor" (que fornece contraexemplos), consegue encontrar um $y$ válido após um número constante de tentativas.
  • Se a teoria provasse a existência de um divisor primo, o teorema KPT garantiria a existência de um algoritmo de tempo polinomial capaz de encontrar um fator primo de um número composto $x = p \cdot q$ (ou produtos de múltiplos primos) com alta probabilidade.

• Protocolos Estudante-Professor:

  • O autor define um protocolo onde o "estudante" tenta adivinhar um divisor primo de um produto de primos $x = p_1 \dots p_d$.
  • O "professor" é uma função que responde às tentativas do estudante, fornecendo informações que forçam o estudante a realizar uma fatoração não trivial.
  • A estratégia do professor baseia-se na análise de campos de conjuntos (fields of sets) gerados pelas respostas do estudante. O professor usa a estrutura de "números óbvios" (números cujas fatorações podem ser derivadas de interseções, uniões e complementos dos números já vistos) para guiar o estudante.

• Análise Combinatória e Probabilística:

  • O autor demonstra que, se o estudante (algoritmo de tempo polinomial) nunca produz um número "não óbvio", ele falha em encontrar um fator primo.
  • Se o estudante produzir um número não óbvio, o autor prova que isso implica que o algoritmo "quebra" um par específico de primos ($p_l p_k$), ou seja, consegue isolar um deles.
  • Utilizando o Lema 3.9 e argumentos de média, mostra-se que se um algoritmo consegue quebrar pares de primos em um protocolo determinístico, ele pode ser convertido em um algoritmo probabilístico de tempo polinomial que fatora produtos de dois primos com probabilidade constante.

• Extensão para $BB(\Sigma^b_0)$:

  • Para a teoria estendida com o esquema de escolha, o autor utiliza uma versão paralela do teorema KPT (de Cook e Thapen).
  • O estudante pode fornecer sequências de candidatos. O autor mostra como "desdobrar" essas consultas paralelas em consultas sequenciais, mantendo o número de rodadas constante, e aplica a mesma lógica de campos de conjuntos para provar que a existência de tal prova implicaria um algoritmo de fatoração eficiente.

4. Resultados Principais

1. Inprovabilidade em PV1:
   Sob a hipótese de que a fatoração é difícil para circuitos de tamanho polinomial, a teoria PV1 não prova a sentença PrimeFactor (todo número $\ge 2$ tem um divisor primo).

   • Consequência: Existe um modelo $\mathcal{M}$ de PV1 contendo um número não padrão $m$ que não possui fatoração prima em $\mathcal{M}$ (todo divisor de $m$ possui um divisor próprio em $\mathcal{M}$).

2. Inprovabilidade em PV1 + $BB(\Sigma^b_0)$:
   O resultado se estende à teoria PV1 aumentada pelo esquema de escolha fortemente limitada. Sob a mesma hipótese, esta teoria estendida também não prova a existência de fatoração prima.

3. Separação de Hierarquia:
   Combinando o resultado com trabalhos anteriores (Cook e Thapen, que assumiram que a fatoração não está em $BPP$ para mostrar $PV1 \nvdash BB(\Sigma^b_0)$), o autor estabelece uma separação estrita sob uma única hipótese de complexidade:
   $$PV1 \subsetneq PV1 + BB(\Sigma^b_0) \subsetneq S^1_2$$
   Isso mostra que a adição do esquema de escolha e a capacidade de provar a existência de fatores primos são estritamente mais fortes que a teoria base PV1.

5. Contribuições Técnicas e Significância

• Conexão entre Lógica e Criptografia: O trabalho fornece uma ligação rigorosa entre a provabilidade em aritmética limitada e a dureza média de problemas de fatoração. Mostra que a incapacidade de provar a existência de fatores primos em teorias fracas é equivalente à dificuldade computacional de fatorar números semiprimos.
• Novos Modelos Não Padrão: O resultado constrói explicitamente (via Teorema da Completude) a existência de modelos de aritmética limitada onde a fatoração prima falha, um fenômeno que não ocorre em modelos de $S^1_2$.
• Domínios de Furstenberg: O autor reinterpreta o resultado em termos de teoria de anéis, mostrando que existem modelos de PV1 + $BB(\Sigma^b_0)$ que não são "partes positivas de domínios de Furstenberg" (domínios onde todo elemento não invertível possui um divisor irredutível).
• Questões Abertas: O artigo levanta questões sobre a separação de níveis superiores da hierarquia de Buss (como $S^1_2$ vs $T^1_2$) usando hipóteses de complexidade que não mencionam explicitamente classes como $NP$ ou $PH$, sugerindo que a dureza da fatoração pode ser uma chave para separar teorias aritméticas mais fortes.

Conclusão

O artigo demonstra que a capacidade de provar a existência de fatoração prima é um limite fundamental para a teoria PV1 e suas extensões imediatas. A prova de que essa propriedade não é derivável depende crucialmente da suposição de que a fatoração de inteiros permanece difícil para algoritmos de tempo polinomial, reforçando a profunda interconexão entre a estrutura lógica da aritmética limitada e a complexidade computacional da criptografia.