Perguntas com a marcação «complexity-theory»

9
Provas interativas para coNP

Estou tentando entender os sistemas interativos de provas e tentei o seguinte problema como exercício. Sabemos que PH⊆PSPACEPH⊆PSPACEPH \subseteq PSPACE e IP=PSPACEIP=PSPACEIP=PSPACE , então crie sistemas de prova interativos (fáceis de entender) para PHPHPH ? Um sistema de prova interativa para...

9
Expressividade de expressões regulares modernas

Recentemente, conversei com um amigo sobre um site que propunha desafios regex, combinando principalmente um grupo de palavras com uma propriedade especial. Ele estava procurando por um regex que corresponda a cadeias de caracteres como ||||||||onde o número de |é primo. Eu imediatamente disse a...

8
Problemas completos para

Sabemos que a poliL não tem problemas completos, pois entraria em conflito com o teorema da hierarquia espacial. Mas: Existem problemas completos para cada nível dessa hierarquia?polyLpolyLpolyL Para ser mais preciso: A classe tem problemas completos em reduções para cada

8
Suposição sobre pesos em circuitos limiares

Uma porta de limite que implementa uma função de limite linear em entradas booleanas é dada pela equação: onde . Os são chamados de pesos da função de limiar e é chamado de limiar e, naturalmente, o gate dispara na entrada se a soma ponderada dada pela equação acima exceder .nnnx1 1,x2......

8
O Papai Noel pode ser justo e eficiente?

Como estabelece a rede sempre-verde A Física do Papai Noel , é fisicamente impossível para o Papai Noel receber um presente para todas as crianças do planeta. O planejamento de rotas não ajuda muito lá, mas pode um bom algoritmo de planejamento garantir que todas as crianças recebam um presente de...

8
A coloração do gráfico 3 é auto-redutível

Estou interessado na auto-redutibilidade do problema do Graph 3-Coloralibity. Definição do problema do gráfico 3-Coloralibity. Dado um gráfico não direcionado GGG existe uma maneira de colorir os nós vermelho, verde e azul para que nenhum nó adjacente tenha a mesma cor? Definição de...