A prova padrão do limite de Chernoff (do livro de algoritmos aleatórios ) usa as funções de desigualdade e geração de momentos de Markov, com um pouco de expansão de Taylor. Nada muito difícil, mas um tanto mecânico. Mas existem outras provas vinculadas a Chernoff que expõem a estrutura mais...
Frequentemente ouvimos falar de pesquisas e publicações clássicas no campo da complexidade computacional (Turing, Cook, Karp, Hartmanis, Razborov etc.). Fiquei me perguntando se existem trabalhos publicados recentemente considerados seminais e uma leitura obrigatória. Por recente eu quero dizer nos...
Mark Dominus coletou alguns exemplos de reduções no tempo polinomial de vários problemas difíceis de NP para correspondência de "expressão regular" . Visualizar verificações em tempo polinomial não é um salto enorme. Como você ilustra a classe NP-complete para estudantes de graduação ou para...
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...
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...
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...
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...
Richard J. Lipton foi selecionado como o vencedor do Prêmio Knuth 2014 "por Introdução de Novas Idéias e Técnicas". Quais são as suas principais idéias e técnicas que Lipton desenvolveu? Nota. Esta questão se tornará um wiki da comunidade. Coloque uma dessas idéias, técnicas ou resultados por...
Provavelmente, alguns paradoxos matemáticos e lógicos poderiam ser automaticamente aplicados aos computadores, mas existem paradoxos descobertos na própria ciência da computação? Por paradoxos, quero dizer resultados contra-intuitivos que parecem uma
Recentemente, um amigo meu (trabalhando no TCS) mencionou em uma conversa que "ele queria ver / conhecer todos (ou tanto quanto possível) os belos resultados do TCS em sua vida". Isso meio que me fez pensar sobre os belos resultados nessa área e, portanto, a motivação para a seguinte...
Uma das coisas boas de ter evoluído em um universo com três dimensões espaciais é que desenvolvemos habilidades de resolução de problemas referentes a objetos no espaço. Assim, por exemplo, podemos pensar em um trigêmeo de números como um ponto em 3-d e, portanto, computação sobre trigêmeos de...
Estou interessado em exemplos de problemas em que um teorema que aparentemente não tem nada a ver com mecânica / informação quântica (por exemplo, afirma algo sobre objetos puramente clássicos) pode, no entanto, ser provado usando ferramentas quânticas. Uma pesquisa Quantum Proofs for The Classems...
Muitas vezes, é possível encontrar métodos de plano de corte, propagação variável, ramificação e encadernação, aprendizado de cláusulas, retrocesso inteligente ou até heurísticas humanas tecidas à mão nos solucionadores SAT. No entanto, há décadas os melhores solucionadores de SAT contam com...
Edit: Eu escolhi a resposta com a pontuação mais alta até 06 de dezembro de 2012. Esta é uma pergunta suave. O conceito de algoritmos (determinísticos) remonta a BC. E os algoritmos probabilísticos? Em esta entrada wiki , o algoritmo de Rabin para o problema mais próximo par de geometria...
Eu sou um cientista da computação fazendo um curso de Topologia (uma pitada de topologia de conjunto de pontos fortemente aromatizada pela teoria do continuum). Interessei-me por problemas de decisão testando uma descrição de um espaço (por simplicidades) para propriedades topológicas; aqueles...
Sobre quais tópicos do TCS ausentes na Wikipedia você mais gostaria de ter um artigo? Podem ser omissões gritantes ou apenas tópicos que você acha que realmente deveriam ter um artigo. Um tópico por resposta, para que os mais procurados possam ser votados. Atualização 5/2/2017 : Shuchi Chawla...
Esta é minha primeira pergunta na pilha de histórias, portanto, não seja muito rude se eu estiver violando a etiqueta de alguma forma) Como sabemos, em matemática, mesmo matemáticos, astros e gênios famosos estão cometendo erros sérios de tempos em tempos. Por exemplo, o teorema de quatro cores e...
É claro que alguns resultados de complexidade podem entrar em colapso para idiomas unários, mas eu me pergunto se existe em algum lugar uma pesquisa resumindo os resultados conhecidos nesse caso: uma espécie de zoológico de complexidade para idiomas unários. Você saberia de tal...
Estarei participando da minha primeira conferência de ciência da computação e, depois de ler os conselhos sobre como melhorar as conferências , notei que várias sugestões eram sobre alunos de pós-graduação que participavam de sua primeira conferência. Que conselho você daria para um estudante de...
Há uma reputação de que, na ciência da computação, não temos livros populares de ciência. Claro que isso não é verdade! (No mesmo espírito da lista de que os livros devem Todo mundo Read? , Que documentos devem todos ler? , O que vídeos deve relógio todos? E inspirado a partir Favorita livro de...