Estou interessado em como alguém prova que uma sentença é relativizada. Evidentemente, provar que uma sentença não se relativiza é simples, como visto no resultado de Baker-Gill-Solovay; mas como provar que uma sentença é relativizada, isto é, verdadeira em relação a qualquer oráculo? Existem...
Enquanto navegava em postagens antigas do CStheory.se , deparei-me com uma fascinante publicação no blog sobre o problema da mortalidade matricial . A menos que eu tenha interpretado mal o problema, ele afirma que, dada uma coleção finita de matrizes 3 x 3 com entradas inteiras para cada valor da...
Dado um gráfico , qual é o número mínimo de arestas de G que precisamos excluir para tornar o triângulo livre? Para meus olhos destreinados, isso parece ser um problema difícil.GGGGGG Esse problema é conhecido como NP-complete? E o analógico para gráficos orientados (isto é, dígrafos sem arestas...
(Publiquei esta pergunta no CS há dez dias, sem resposta desde então - então publico aqui.) Qualquer fórmula CNF pode ser transformada em tempo polinomial em uma fórmula 3-CNF usando novas variáveis. Nem sempre é possível se novas variáveis não são permitidas (por exemplo, a fórmula de cláusula...
Estou procurando uma referência para "reduzir" reduções de Turing a muitas reduções. Tenho em mente uma declaração da seguinte forma (declarações suficientes semelhantes também me satisfariam): Teorema. Se , então A ≤ 2 f m B t t .A ≤fTBA≤TfB\mathsf{A}\leq_T^f \mathsf{B}A ≤2fmBt tA≤m2fBtt\mathsf...
Nota: Postei uma pergunta semelhante sobre o gráfico não direcionado . Dado Um dígrafo sem arestas múltiplas ou loopsGGG Um nó de origemsss Um nó de destinottt Comprimento máximo do caminholll Estou procurando por - um subgrafo de que contém qualquer nó e qualquer aresta em (e somente...
Qual é o algoritmo mais rápido conhecido por fatorar polinômios com nnn variáveis e grau total ≤d≤d\leq d ? Aqui, nnn está crescendo ddd é fixo. A maioria dos trabalhos parece considerar o caso quando ddd está crescendo e nnn é fixo. Estou interessado em resultados tanto em campos finitos quanto...
Alguém já pensou na possibilidade de uma linguagem de programação e de um compilador, de modo que o compilador possa fazer automaticamente a análise assintótica do pior caso? O caso de uso que tenho em mente é uma linguagem de programação na qual escrevo código e compilo. O compilador me diz que...
Uma maneira de provar a NP coNP é mostrar que, para todo sistema de prova proposicional computável em tempo polinomial, existe uma família de tautologias para a qual requer comprimentos de super polinômios (em comparação ao comprimento da tautologia sendo comprovada). Resultados como o de Haken e...
Um código de autenticação de mensagem (MAC) é definido por um triplo de algoritmos eficientes , que satisfazem o seguinte (a definição é a da secção 4.3 dolivro Katz-Lindell) :(Gen,MAC,Verif)(Gen,MAC,Verif)(\mathsf{Gen}, \mathsf{MAC}, \mathsf{Verif}) Na entrada , o algoritmo G e n gera uma...
Existe um naturais problema gráfico -completo, que permanece N P -Complete mesmo quando é restrita a qualquer classe gráfico reconhecível de tempo polinomial? Para evitar casos degenerados, consideremos apenas classes gráficas densas , nas quais o número de gráficos não isomórficos ≤ n -vertex...
Considere o seguinte problema: Entrada: (G1, G2) em que G1 e G2 são gráficos não direcionados Pergunta: O tamanho do conjunto independente máximo de G1 é pelo menos tão grande quanto o tamanho do conjunto independente máximo de G2? Parece uma pergunta bastante natural, e ainda assim não consegui...
Estou trabalhando para tentar particionar um gráfico triangulado em subgráficos conectados com algumas garantias sobre o número de arestas entre partições. Aqui está um exemplo de um gráfico triangulado que foi particionado em 4 "clusters": O que eu queria originalmente era um algoritmo que...
O número cromático é definido no artigo Partições de gráficos em cografias . Ele solicita o número mínimo de cores usadas para colorir vértices, de modo que cada classe de cores seja uma cografia . Cograph é um gráfico livre de P4 , ou seja, não há caminho induzido de comprimento 3. O papel indica...
Recentemente, houve novos resultados em estudos experimentais baseados em computador do Problema da Discrepância de Erdos (EDP) (via solucionadores SAT, citados abaixo). Esse problema foi citado e estudado por vários pesquisadores (T) de CS. No entanto, os links (possivelmente profundos?) Para (T)...
Conjeturo que, se é um gráfico livre de triângulo simples, em seguida, existe um conjunto de, no máximo, n 2 / 25 bordas cuja eliminação destrói cada ciclo estranho.GG G n2/ 25n2/25 n^2/25 Para obter mais informações, consulte o artigo de Erdös et al., 1988, Como fazer um gráfico bipartido...
De acordo com o teorema BGS [1], existe um oráculo tal que P Um ≠ N P A .AAAPA≠NPAPA≠NPAP^A\neq NP^A Se a operação de relativização fosse uma função bem definida, seria de esperar que, a partir de B A ≠ C A, seria possível concluir que B ≠ C , por exemplo, P ≠ N P seguiria o BGS. No entanto, P ≠ N...
A complexidade do espaço monótono de uma linguagem pode ser definida em termos de redes de comutação monótonas (consulte, por exemplo, "Limites inferiores médios de caso para redes de comutação monotônicas" por Filmus et al.). Essa noção está vinculada à hierarquia N C monótona e pode ter...
O problema do subgráfico conectado de peso máximo é o seguinte: Entrada: um gráfico e um peso (possivelmente negativo) para cada vértice .w i i ∈ VG = ( V, E)G=(V,E)G=(V,E)WEuWEuw_ii ∈ VEu∈Vi \in V Saída: um subconjunto de peso máximo de vértices, de modo que esteja conectado.G [ S ]SSSG [...
Tenho tido muita dificuldade em encontrar uma referência que dê uma explicação simples e direta do seguinte: Suponha que tenhamosnnn variáveis aleatóriasY1,…,YnY1,…,YnY_1, \dots, Y_n , cada uma combbb bits de comprimento. (Ou seja, com valores em{0,…,2b−1}{0,…,2b−1}\{0, \dots, 2^b-1 \} )....