todo mundo sabe que existem muitos problemas de decisão que são difíceis de NP em gráficos gerais, mas estou interessado em problemas que são difíceis de NP quando o gráfico subjacente é um caminho. Então, você pode me ajudar a coletar esses problemas? Eu já encontrei uma pergunta relacionada...
Muitos problemas de gráficos algorítmicos podem ser resolvidos em tempo polinomial, tanto em gráficos não ponderados quanto em ponderados. Alguns exemplos são caminho mais curto, árvore de abrangência mínima, caminho mais longo (em gráficos acíclicos direcionados), fluxo máximo, corte mínimo,...
Essa é uma pergunta em aberto - pela qual peço desculpas antecipadamente. Existem exemplos de declarações que (aparentemente) não têm nada a ver com complexidade ou máquinas de Turing, mas cuja resposta implicaria ?P≠NPP≠NP\mathbf{P}\neq
Na sequência de uma pergunta anterior , Quais são os melhores limites inferiores do espaço atual para o SAT? Com um limite inferior do espaço, quero dizer aqui o número de células da worktape usadas por uma máquina de Turing que usa um alfabeto binário da worktape. Um termo aditivo constante é...
No artigo "A COMPLEXIDADE DOS PROBLEMAS DE SATISFIABILIDADE", de Thomas J. Schaefer, o autor mencionou que This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the...
Eu li que, inicialmente, Church propôs o cálcio como parte de seu artigo Postulados da Lógica (que é uma leitura densa). Mas Kleene provou seu "sistema" inconsistente, após o qual Church extraiu coisas relevantes por seu trabalho sobre "computabilidade efetiva" e abandonou seu trabalho anterior...
Eu estava lendo o artigo de Andrej Bauer Primeiros Passos na Teoria da Computabilidade Sintética . Na conclusão, ele observa que Nossa axiomatização tem seu limite: não pode provar nenhum resultado na teoria da computabilidade que falhe em relativizar os cálculos da Oracle. Isso ocorre porque a...
Na presente discussão , tentativa de Norbet Blum prova é sucintamente refutada por notar que a função Tardos é um contra-exemplo Teorema 6.P≠NPP≠NPP \neq NP Teorema 6 : Let ser qualquer função monótona booleano. Suponha que exista um aproximador de CNF-DNF A que possa ser usado para provar um...
Seja as variáveis . A distância entre duas variáveis é definida como d ( x a , x b ) = | a - b | . A distância entre dois literais é a distância entre as duas variáveis correspondentes.x1,x2,x3...xnx1,x2,x3...xnx_1 , x_2 , x_3 ... x_nd(xa,xb)=|a−b|d(xa,xb)=|a−b|d(x_a , x_b) = |a-b| Suponha que...
Existe uma boa pesquisa que compara diferentes extratores, concentradores e superconcentradores e estabeleça os melhores métodos em termos de troca entre aleatoriedade, tempo e espaço?
Uma prova de separação de classes de complexidade usa uniformidade de classes de complexidade essencialmente se a prova não provar o resultado da versão não uniforme, por exemplo, provas baseadas em diagonalização (como teoremas da hierarquia de tempo e espaço) fazem uso essencial da uniformidade,...
Sabemos muito sobre as limitações dos circuitos de profundidade constante (tamanho polinomial). Como as fórmulas de profundidade constante (tamanho polinomial) são um modelo de computação ainda mais restrito, todos os problemas que não se encontram no AC 0 também não são computáveis por uma...
Que diferenças interessantes existem entre teoria e prática de segurança e criptografia? O mais interessante será, obviamente, exemplos que sugerem novos caminhos para a pesquisa teórica com base na experiência prática :). As respostas podem incluir (mas não estão limitadas a): Exemplos em que...
Se é uma função convexa, a desigualdade de Jensen indica que e mutatis mutandis quando é côncavo. Claramente, na pior das hipóteses, você não pode limitar em termos de para um convexo , mas existe um limite que segue nessa direção se é convexo, mas "não muito convexo"? Existe algum limite padrão...
Já publiquei essa pergunta há algum tempo no MathOverflow , mas, pelo que sei, ela ainda está aberta, por isso estou publicando-a aqui na esperança de que alguém possa ter ouvido falar dela. Declaração do problema Seja , e três partes em partes não vazias (indicadas por 's, ' e 's) do conjunto {...
Alguém poderia apontar para um ou mais sites onde é possível fazer o download de uma implementação de trabalho de um solucionador #SAT? Estou interessado em retornar a contagem exata da solução, não em uma
O BQP é igual ao BPP com acesso a um oráculo de subgrupo oculto da
Ao reunir resultados, geralmente é desejável ter alguns diagramas de aparência profissional, em vez de diagramas reunidos no MS Paint. Qual é o padrão para desenhar estruturas de
(Von Neumann deu um algoritmo que simula uma moeda justa, tendo acesso a moedas tendenciosas idênticas. O algoritmo potencialmente requer um número infinito de moedas (embora, na expectativa, finitas sejam suficientes). Essa questão diz respeito ao caso em que o número permitido de lançamentos...
Preâmbulo Os sistemas interativos de prova e os protocolos Arthur-Merlin foram introduzidos por Goldwasser, Micali e Rackoff e Babai em 1985. No início, pensava-se que o primeiro era mais poderoso que o segundo, mas Goldwasser e Sipser mostraram que tinham o mesmo poder ( em relação ao...