Decidindo o bit mais significativo da multiplicação binária

10

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 1l doisl1l2l1l2

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 1l 2 D L o g o t i m e t C 0 D L o g o t i m eil1l2DLogTime TC0DLogTime TC0 0-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?DeuogTEume D L o g T i m eTC0 0DeuogTEume TC0 0

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).TC0 0

Heyheyhey
fonte
Há uma prova no livro Complexidade Descritiva iirc. Não sei ao certo o que você quer dizer com o bit mais significativo, ele sempre é um por definição.
Kaveh
Isso é apenas uma piada do seu professor: os bits são 0 ou 1, e o bit mais significativo é o bit não 0 na posição mais alta. É igual a 1 por definição (a menos que um dos fatores e seja zero). l 2eu1 1eu2
Gamow
@ Kaveh Obrigado pela referência: eu vou dar uma olhada. Desculpe a confusão sobre o bit mais significativo. Estou implicitamente assumindo que o resultado é impresso em 2m-1 bits e, se necessário, com 0 iniciais.
precisa saber é o seguinte
@ Kaveh: no livro de complexidade descritiva, apenas o limite superior é mencionado. Não consegui encontrar nada sobre dureza da multiplicação binária, no entanto.
Heyheyhey 28/08
Você escreve: "Além disso, parece bem sabido que a multiplicação binária já é - uniforme -hard." Por que parece isso? Eu sei que a multiplicação binária não está em , e é com isso que me preocupo atualmente. DeuogTEume TC0 0UMAC0 0
Thomas Klimpel

Respostas:

6

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 .TC0AC0MajorityCount

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 tF SCountMulta0a1ankaiabaaik>3nabFO .CountFO(Mult)

Kaveh
fonte
11
Obrigado pelas respostas! Sim, isso verifica se a multiplicação binária está completa para o TC0. Quanto ao bit mais significativo, ainda existem alguns problemas. O bit mais significativo da multiplicação (111 x 111) = 110001 é 1 e, para este (100 x 100) = 010000, é 0. Observe que os bits mais significativos dos multiplicandos são os mesmos nos dois casos. Portanto, não creio que, em geral, seja suficiente adicionar os bits mais significativos. Estou esquecendo de algo?
heyheyhey
11
Se e y = 2 n + 1 / 2 , em seguida, o MSB dos x 2 é 0, e o MSB de Y 2 representa um, ainda que x e y podem apenas diferem em um pouco menos significativo. x=2n+1/2y=2n+1/2x2y2xy
Emil Jerabek
3
A edição não está correta. Como estamos adicionando números m, pode haver apenas um pouco de carry, mas log m. Decidir quanto dele se propaga é muito mais difícil.
Emil Jerabek
11
De fato, desconsiderar todo o resto: calcular a execução de uma única posição (digamos, em algum lugar no meio) já é equivalente a Count, portanto, TC ^ 0-complete.
Emil Jerabek
11
@ Heyheyhey, a fórmula que escrevi é FO e, portanto, em AC0 uniforme.
Kaveh