Pergunto-me, qual é (atualmente) o maior número , de modo que um problema natural seja conhecido com as seguintes propriedades:kkk Um algoritmo já foi encontrado para o problema.O(nk)O(nk)O(n^k) Para qualquer fixo não algoritmo é conhecido para o mesmo problema. (Observe que um algoritmo mais...
Sabemos que, se você possui uma máquina PSPACE, ela é poderosa o suficiente para fornecer uma prova interativa de qualquer nível da hierarquia polinomial. (E se bem me lembro, tudo o que você precisa é #P.) Mas suponha que você queira fornecer uma prova interativa de associação em um idioma. É...
No artigo A hipótese aleatória do Oracle é falsa , os autores (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan e Rohatgi) discutem as implicações da hipótese do oráculo aleatório . Eles argumentam que sabemos muito pouco sobre separações entre classes de complexidade, e a maioria dos resultados...
É impossível escrever uma linguagem de programação que permita todas as máquinas que param em todas as entradas e nenhuma outra. No entanto, parece ser fácil definir uma linguagem de programação para qualquer classe de complexidade padrão. Em particular, podemos definir uma linguagem na qual...
Há uma justificativa filosófica frequentemente citada para acreditar que P! = NP mesmo sem prova. Outras classes de complexidade têm evidências de que são distintas, porque, se não, haveria consequências "surpreendentes" (como o colapso da hierarquia polinomial). Minha pergunta é: qual é a base...
Defina LOGLOG como a classe de idiomas que pode ser calculada no espaço O (loglog n) por uma máquina de Turing determinística (com acesso bidirecional à entrada). Da mesma forma, defina NLOGLOG como a classe de idiomas que pode ser calculada no espaço O (log log n) por uma máquina de Turing não...
Nesta pergunta, uma fórmula 3CNF significa uma fórmula CNF em que cada cláusula envolve exatamente três variáveis distintas . Para um constante 0 < s <1, Gap-3SAT s é o seguinte problema de promessa: Gap-3SAT s Instância : Um 3CNF fórmula φ. Sim, prometo : φ é satisfatório. Sem promessa :...
Esta pergunta é sobre problemas para os quais existe uma grande lacuna de complexidade aberta entre o limite inferior e o limite superior conhecidos, mas não devido a problemas abertos nas próprias classes de complexidade. Para ser mais preciso, digamos que um problema tenha classes de lacunas...
Eu estava (e ainda estou) realmente interessado na resposta a essa pergunta, porque essa é uma variação interessante da complexidade dos jogos que não foi resolvida, então eu ofereci uma recompensa. Eu pensei que a pergunta original provavelmente era muito difícil, então eu postei três perguntas...
Existem toneladas de problemas completos de NP e fontes que os coletam, por exemplo, consulte o livro de Garey e Johnson. Eu também estaria interessado em ver uma lista dos problemas completos do NEXP. Existe um disponível? Como suponho que não exista, abro esta pergunta (é suposto ser um wiki da...
Neste post convidado por Josh Grochow, no blog de complexidade, ele relata um recente workshop dedicado ao GCT, realizado em Princeton em julho. Vários participantes argumentaram que deveríamos usar o GCT para atacar problemas mais fáceis do que vs. , a fim de criar intuição e ver se o método tem...
Deixei L={n:the nth binary digit of π is 1}L={n:the nth binary digit of π is 1}L = \{ n : \text{the }n^{th}\text{ binary digit of }\pi\text{ is }1 \} (onde é considerado codificado em binário). Então, o que podemos dizer sobre a complexidade computacional de L ? É claro que L ∈ E X P . E, se não...
Decidir se uma fórmula booleana quantificada, como ∀ x1∃ x2∀ x3⋯ ∃ xnφ ( x1, x2, … , Xn) ,∀x1∃x2∀x3⋯∃xnφ(x1,x2,…,xn),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), sempre avalia como verdadeiro é um problema clássico completo do PSPACE. Isso pode ser visto...
Eu pensei em compartilhar esta pergunta, pois pode ser interessante para outros usuários aqui. Assume-se que uma função que é de uma classe uniforme (como ) também está em uma pequena classe não uniforme (como um C 0 / p o l y , isto é, não uniforme Um C 0 ), isso implica que a função está contido...
ST-Conectividade é o problema de determinar se existe um caminho entre dois vértices dirigidos distintos e em um grafo orientado G (V, E) . Se esse problema pode ser resolvido no espaço de logs, é um problema aberto de longa data. Isso é chamado de problema NL vs L.ssstttG ( V,...
Supondo que P! = NP, acredito que tenha sido demonstrado que existem problemas que não estão em P e nem em NP-Complete. O isomorfismo do gráfico é conjecturado como um problema. Existe alguma evidência de mais dessas "camadas" no NP? isto é, uma hierarquia de mais de três classes começando em P e...
Defina - para ser a classe de idiomas modo que exista um idioma e para infinitos , e concordar em todos os casos de comprimento . (Ou seja, esta é a classe de idiomas que pode ser "resolvida infinitamente com frequência, em tempo
Eu gostaria de encontrar um algoritmo de tempo polinomial que determine se o intervalo de um determinado conjunto de matrizes contém uma matriz de permutação. Se alguém souber se esse problema é de uma classe de complexidade diferente, isso seria igualmente útil. EDIT: Marquei esta questão com...
Qualquer número natural pode ser considerado como uma sequência de bits; portanto, inserir um número natural é o mesmo que inserir uma sequência 0-1; portanto, problemas NP-completos com entradas naturais obviamente existem. Mas existem problemas naturais, ou seja, aqueles que não usam codificação...
Citando a Wikipedia , "[O Jogo da Vida de Conway] tem o poder de uma máquina de Turing universal: ou seja, qualquer coisa que possa ser computada algoritmicamente pode ser computada no Jogo da Vida de Conway". Esses resultados se estendem a versões barulhentas do Jogo da Vida de Conway? A versão...