Complexidade da circunferência: circuito monótono da função Maioria

8

Como mostrado no artigo "Circuitos monótonos para a função majoritária", é possível construir um circuito booleano monótono para a função majoritária em n variáveis ​​com tamanho O (n ^ 3) e profundidade 5,3 log (n) + O (1).

http://link.springer.com/chapter/10.1007/11830924_38

Minha pergunta é: qual é a complexidade temporal dessa construção? (ou seja, o tempo necessário para construir o circuito, dado n em unário)

Alan Carneiro
fonte

Respostas:

-1

A complexidade do tempo é geralmente definida como o "número de operações no pior dos casos para uma máquina de Turing". O modelo de computação de circuito monótono não é o modelo de tempo de Turing. Portanto, não faz sentido dizer qual é a complexidade do tempo de um circuito desse tipo.

Por outro lado, se vemos o modelo de circuito monótono como um modelo de circuitos reais, então um "custo de tempo" da computação é a profundidade de tal circuito. Assim, nesse sentido, a complexidade de tempo do circuito mencionado é de 5,3log (n).

É claro que, em circuitos reais, existem outros fatores além da "profundidade" que contribuem para "quanto tempo leva para fazer o cálculo". Por exemplo, o fio mais longo de um circuito geralmente é um gargalo na computação VLSI real, pois sua capacitância maior leva mais tempo para carregar.

Chris Blake
fonte
6
A questão pede a complexidade temporal da "construção". Embora não esteja claro, entendi o tempo necessário para construir o circuito, dado n em unário. Parece uma pergunta razoável para mim. Em particular, a construção é polytime aleatória, e é interessante perguntar se pode ser feita subexponencial determinística.
Emil Jerabek