Análogo exponencial da NC?

8

A classe de Nick (NC) é a classe de problemas que podem ser resolvidos em tempo de poliolog usando um número polinomial de processadores.

Quero saber sobre o analógico exponencial, que abrangeria problemas que podem ser decididos em tempo polinomial usando um número exponencial de processadores.

O que estou procurando é um nome para esta classe e quaisquer relações conhecidas entre essa classe e outras classes de complexidade ou quaisquer problemas canônicos para a classe. Parece simples que conteria NP e co-NP, e acho que está contido no PSPACE, mas não tenho muita certeza sobre isso.

complexity-theory reference-request parallel-computing complexity-classes Kurt Mueller
fonte
8
Eu escrevi uma resposta, mas depois achei respondida aqui: cstheory.stackexchange.com/questions/6753/...
MDXN

Respostas:

1

O tempo em circuitos corresponde à profundidade. Portanto, por tempo polinomial significa profundidade polinomial.

O número de processadores é o tamanho do circuito, ou seja, o número de portas no circuito. Portanto, pelo número exponencial de processadores, você permite o tamanho exponencial. Essa seria a classe . Mas todas as funções já estão em (pense no CNF da função que você deseja calcular).DepthSEuze(nO(1),2nO(1))DepthSEuze(2,2nO(1))

O fato é que o número exponencial de processadores é muito forte para ser útil por si só.

Uma restrição razoável a ser colocada é limitar a quantidade de comunicação entre diferentes processos. Por exemplo, cada processo só pode se comunicar com muitos outros processos polinomialmente e as mensagens têm tamanho polinomial. Isso seria conforme explicado nas respostas à pergunta de Aterm sobre a história . Outra maneira de lembrar que , problemas computáveis ​​alternando as máquinas de Turing no tempo polinomial. A alternância nas máquinas de Turing é essencialmente bifurcar novos processos e, em seguida, ingressar depois que eles terminam assumindo a conjunção / disjunção de seus valores de retorno.PSpumacePSpumace=UMATEume(nO(1))

Kaveh
fonte
É possível obter o PSPACE, mesmo quando a única restrição à comunicação é o tempo limite.
@ Ricky, isso realmente depende do modelo. Se o modelo estiver alternando a máquina de Turing, sim, como escrevi na minha resposta. Se são circuitos gerais (os circuitos NC não uniformes), não são. O tempo limite para os circuitos é profundidade e qualquer função é computável por uma profundidade 2 CNF.
Kaveh
O OP especificou o modelo como máquina paralela.
@ Ricky, o que você quer dizer com "máquina paralela"? Existem muitos modelos que tentam capturar a noção de computação paralela. Por exemplo, tome PRAM . O OP pergunta sobre NC, que é uma classe de circuitos e escreve o que afirmei.
Kaveh
Quero dizer essencialmente PRAM. O OP diz que NC "é a classe de problemas que podem ser decididos em tempo de poliolog usando um número polinomial de processadores" e pergunta sobre "problemas que podem ser decididos em tempo polinomial usando um número exponencial de processadores".