Eu tenho uma base muito forte em álgebra, a saber álgebra comutativa, álgebra homológica, teoria de campo, teoria da categoria, e atualmente estou aprendendo geometria algébrica. Sou formado em matemática, com tendência a mudar para a ciência da computação teórica. Tendo em mente os campos...
O problema central da teoria da complexidade é indiscutivelmente vs .PPPNPNPNP Entretanto, como a natureza é quântica, parece mais natural considerar as classes (ou seja, problemas de decisão solucionáveis por um computador quântico em tempo polinomial, com uma probabilidade de erro de no máximo...
Nós "sabemos" que é nomeado para Steve Cook e é nomeado para Nick Pippenger. Se não me engano, Steve Cook nomeou NC em homenagem a Nick Pippenger, e me disseram que o inverso também é verdadeiro. No entanto, não pude encontrar nenhuma evidência desse último fato no artigo de Steve Cook sobre as...
Embora tenha passado em alguns cursos sobre teoria das probabilidades, tanto no ensino médio quanto na universidade, tenho dificuldade em ler os artigos da TCS quando se trata de probabilidade. Parece que os autores dos trabalhos do TCS estão muito familiarizados com a probabilidade. Eles...
Preciso de um livro de teoria de autômatos finito com muitos exemplos que eu possa usar para auto-estudo e preparação para
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...
Isenção de responsabilidade: só posso garantir meus campos de pesquisa, como métodos formais, semântica e teoria da linguagem de programação. A situação é possivelmente diferente em outras partes da disciplina. Parece que o TCS se tornou bastante orientado para conferências. Pesquisadores...
Examinar perguntas através da lente algorítmica (isto é, do ponto de vista algorítmico ou da complexidade) tornou-se útil em disciplinas fora do 'domínio padrão' da ciência da computação. Em particular, o CS causou impacto na biologia através da biologia computacional, na física através do...
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...
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 :...
Ocasionalmente, ouvi pessoas falarem sobre algoritmos quânticos e sobre estados e a capacidade de considerar várias possibilidades ao mesmo tempo, mas nunca consegui alguém para explicar o modelo computacional por trás disso. Para ser claro, não estou perguntando como os computadores quânticos são...
Existe uma estrutura de dados da fila prioritária que ofereça suporte às seguintes operações? Inserir (x, p) : adiciona um novo registro x com prioridade p StableExtractMin () : retorne e exclua o registro com prioridade mínima, quebrando os vínculos por ordem de inserção . Assim, após Inserir...
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...
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...
Tenho alguma experiência em computação científica e usei extensivamente kd-trees para aplicativos BSP (particionamento de espaço binário). Recentemente, familiarizei-me com octrees, uma estrutura de dados semelhante para particionar espaços euclidianos em 3D, mas que funciona em intervalos...
É 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...
Duas das suposições comuns para provar resultados de dureza de aproximação são e Unique Games Conjecture. Existe alguma dureza de resultados de aproximação assumindo ? Estou procurando o problema modo que "é difícil aproximar um fator menos que ".P≠NPP≠NPP \neq NPNP≠coNPNP≠coNPNP \neq...
No espírito de algumas discussões gerais como esta , estou abrindo este tópico com a intenção de reunir opiniões sobre quais são os desafios em aberto e os tópicos mais importantes da pesquisa em linguagens de programação . Espero que a discussão possa trazer à tona opiniões sobre o futuro da...
Existe um limite reverso de Chernoff que limita que a probabilidade de cauda seja pelo menos tanta. ou seja, se são variáveis aleatórias binomiais independentes e . Então podemos provar para alguma função .X1,X2,…,XnX1,X2,…,XnX_1,X_2,\ldots,X_nμ=E[∑ni=1Xi]μ=E[∑i=1nXi]\mu=\mathbb{E}[\sum_{i=1}^n...
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...