Estou interessado em determinar a complexidade do seguinte problema de decisão: Dados dois inteiros e (cada um com no máximo m bits), decida se o bit mais significativo da multiplicação é 1 (onde o resultado é impresso em 2m bits com 0s possivelmente à frente)?l 2 l 1 ⋅ l dois
Alguns antecedentes do problema: Obviamente, esse problema é um caso especial de multiplicação binária que pergunta se o ésimo bit da multiplicação é 1. Em seu artigo, circuitos de limiar de profundidade constante uniformes para divisão e multiplicação iterada , Hesse, Allender e Barrington provam que a multiplicação iterada (e, portanto, binária) está em - uniforme . Além disso, parece ser sabido que a multiplicação binária já é - uniformel 1 ⋅ l 2 D L o g o t i m e t C 0 D L o g o t i m e -Difícil. No entanto, não consegui encontrar uma fonte específica que comprove esse resultado de dureza. Como não especialista em complexidade de circuitos, também gostaria de receber um ponteiro para esse resultado geral de dureza. Finalmente, supondo que a multiplicação binária seja - uniforme -hard, minha pergunta também pode ser lida como: Ela permanece - uniforme - difícil se quisermos decidir apenas o bit mais significativo da multiplicação binária? D L o g T i m e
ATUALIZAÇÃO: A resposta de Kaveh esclarece por que a multiplicação binária é -hard (redução de COUNT). A complexidade precisa de decidir o bit mais significativo da multiplicação binária permanece em aberto (e a recompensa é para esta pergunta).
fonte
Respostas:
A multiplicação está completa para e este é um resultado bem conhecido. A redução é de Count (número de 1 bits em um número binário). A comparação de números binários está em portanto é redutível a .TC0 AC0 Majority Count
Para reduzir para faça o seguinte: considere a entrada como . Insira 0s entre a i se chame a . Multiplique por b, que é como a, exceto que a i s nele é substituído por 1s. Escolha k > 3 n . O número na seção do meio de a b é a resposta. A redução é em F S e mostra que C o u n t ∈ F SCount Mult a0a1…an k ai a b a ai k>3n ab FO .Count∈FO(Mult)
fonte