A postagem no blog de Scott Aaronson hoje deu uma lista de problemas / tarefas abertos interessantes em complexidade. Um em particular chamou minha atenção: Crie uma biblioteca pública de instâncias 3SAT, com o menor número possível de variáveis e cláusulas, que teria consequências notáveis...
Faz sentido considerar uma categoria de todos os problemas completos de NP, com morfismos como reduções de politempo entre diferentes instâncias? Alguém já publicou um artigo sobre isso e, em caso afirmativo, onde posso
Corrija um número inteiro nnn e alfabeto Σ = { 0 , 1 }Σ={0,1}\Sigma=\{0,1\} . Defina D FA ( n )DFA(n)DFA(n) como a coleção de todos os autômatos de estados finitos em nnn estados com o estado inicial 1. Estamos considerando todos os DFAs (não apenas os conectados, mínimos ou não degenerados);...
Em seu livro Boolean Function Complexity, Stasys Jukna menciona (página 564) que Kolmogorov acreditava que toda linguagem em P possui circuitos de tamanho linear. Nenhuma referência é mencionada e não consegui encontrar nada online. Alguém sabe mais sobre
Vamos fixar uma codificação sem prefixo de máquinas de Turing e uma máquina de Turing universal que na entrada (codificada como o código sem prefixo de seguido de ) produza o que produz na entrada (possivelmente ambos correndo para sempre). Defina a complexidade de Kolmogorov de , , como a duração...
Existem exemplos de brinquedos que fornecem insights 'essenciais' para a compreensão das três barreiras conhecidas ao problema - relativização, provas naturais e algebrização?P=NPP=NPP =
Considere o problema 3-SAT em n variáveis. O número de possíveis cláusulas distintas é: C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text. O número de casos de problemas é o número de todos os subconjuntos do...
Só conheço duas provas do lema de Schwartz – Zippel. A primeira prova (mais comum) é descrita na entrada da Wikipedia . A segunda prova foi descoberta por Dana Moshkovitz. Existem outras provas que usam idéias substancialmente diferentes?
Sabemos que (ver, por exemplo, Teoremas 1 e 3 de [1]), grosso modo, sob condições adequadas, funções que podem ser computadas eficientemente pela máquina de Turing em tempo polinomial ("computável eficientemente") podem ser expressas por redes neurais polinomiais com tamanhos razoáveis e,...
Editar : Como Ravi Boppana corretamente apontou em sua resposta e Scott Aaronson também acrescentou outro exemplo em sua resposta , a resposta a essa pergunta acabou sendo "sim" de uma maneira que eu não esperava. Primeiro, pensei que eles não responderam à pergunta que eu queria fazer, mas, depois...
Em muitos domínios, existem técnicas canônicas que todo mundo que trabalha no campo deve dominar. Por exemplo, para reduções do espaço de log, o "truque de bit" para composição que consiste em não construir a saída completa da função composta, mas sempre pedindo para recalcular o resultado para...
O que são "regiões fáceis" para garantir a satisfação? Em outras palavras, condições suficientes para que algum solucionador SAT seja capaz de encontrar uma tarefa satisfatória, assumindo que ela exista. Um exemplo é quando cada cláusula compartilha variáveis com poucas outras cláusulas, devido...
Eu gostaria de perguntar sobre um caso especial da pergunta “ Decidir se um determinado circuito NC 0 calcula uma permutação ” por QiCheng que foi deixada sem resposta. Um circuito booleano é chamado de circuito NC 0 k se cada porta de saída depende sintaticamente da maioria das k portas de...
Dado um por matriz binária (as entradas são ou ), o problema é determinar se existem dois vetores binários tais que (todas as operações executadas em ). Este problema é NP-difícil?mmmnnnMMM000111 M v 1 = M v 2 Zv1≠v2v1≠v2v_1 \ne v_2Mv1=Mv2Mv1=Mv2Mv_1 = Mv_2ZZ\mathbb{Z} Está claramente em NP, pois...
Paridade-L é o conjunto de idiomas reconhecidos por uma máquina de Turing não determinística que só pode distinguir entre um número par ou um número ímpar de caminhos de "aceitação" (em vez de um número zero ou diferente de zero de caminhos de aceitação) e que é ainda mais restrito ao trabalho no...
Na complexidade computacional, existe uma distinção importante entre cálculos monótonos e gerais e um famoso teorema de Razborov afirma que 3-SAT e até MATCHING não são polinomiais no modelo monótono de circuitos booleanos. Minha pergunta é simples: existe um análogo quântico para circuitos...
Esta questão foi migrada do Computer Science Stack Exchange porque pode ser respondida no Theoretical Computer Science Stack Exchange. Migrou há 6 anos . Parece que muitas pessoas acreditam que P≠NP∩coNPP≠NP∩coNPP \ne NP \cap coNP , em parte porque acreditam que o...
Peter Shor mostrou que dois dos mais importantes problemas intermediários de NP, fatoração e o problema de log discreto, estão no BQP. Por outro lado, o algoritmo quântico mais conhecido para SAT (busca de Grover) produz apenas uma melhoria quadrática em relação ao algoritmo clássico, sugerindo que...
Quero saber se a não uniformidade ajuda na prática as funções de computação. É fácil mostrar que existem funções em P / p o l y - P , assuma qualquer função incontestável f e considere a linguagem { 0 f ( n ) : n ∈ ω }, que claramente possui circuitos não uniformes simples, mas não é computável de...
Ao ler o artigo "É hora de declarar vitória na contagem da complexidade?" no blog "Godel's Lost Letter and P = NP" , eles mencionaram a dicotomia para CSP's. Depois de algum link a seguir, pesquisando e pesquisando, encontrei o Teorema de Ladner : Teorema de Ladner: Se , então existem problemas...