EDITAR EM 10/12/08:
Tentarei modificar a pergunta para que mais pessoas possam compartilhar suas opiniões. PRECISAMOS de suas contribuições!
Este post é inspirado no do MO: Exemplos de falsas crenças comuns em matemática . Às vezes, grandes listas geram um grande número de respostas cujas qualidades são difíceis de controlar, mas após o sucesso do post relacionado no MO, estou convencido de que seria útil listar um monte de falsas crenças comuns no TCS.
Ainda assim, como o site foi desenvolvido para responder a perguntas de nível de pesquisa, exemplos como significa tempo não polinomial não devem estar na lista. Enquanto isso, queremos alguns exemplos que podem não ser difíceis, mas sem pensar em detalhes, parece razoável também. Queremos que os exemplos sejam educacionais e geralmente aparecem quando se estuda o assunto pela primeira vez.
Quais são alguns exemplos (não triviais) de falsas crenças comuns na ciência da computação teórica que aparecem para as pessoas que estudam nessa área?
Para ser preciso, queremos exemplos diferentes de resultados surpreendentes e contra - intuitivos no TCS; esses tipos de resultados tornam as pessoas difíceis de acreditar, mas são VERDADEIRAS. Aqui estamos pedindo exemplos surpreendentes de que as pessoas podem pensar que isso é verdade à primeira vista, mas depois de um pensamento mais profundo a falha interna é exposta.
Como um exemplo de respostas adequadas na lista, este vem do campo de algoritmos e teoria dos grafos:
Para um gráfico nó , um separador edge é um subconjunto de arestas de tamanho , em que os nós de podem ser particionados em duas partes não adjacentes, cada uma consistindo em no máximo nós . Temos o seguinte "lema":
Uma árvore possui um separador de 1 extremidade.
Direito?
Respostas:
Essa é comum à geometria computacional, mas endêmica em outros lugares: os algoritmos da RAM real podem ser transferidos para a RAM inteira (para restrições inteiras do problema) sem perda de eficiência. Um exemplo canônico é a afirmação “A eliminação gaussiana é executada em .” De fato, ordens de eliminação descuidadas podem produzir números inteiros com muitos bits exponencialmente .O ( n3)
Pior ainda, mas ainda infelizmente comum: os algoritmos da RAM real com a função floor podem ser transferidos para a RAM inteira sem perda de eficiência. De fato, um piso de RAM + real pode resolver qualquer problema no PSPACE ou no #P em um número polinomial de etapas .
fonte
Acabei de acabar com outro mito, o que é contribuído pela resposta de @ XXYYXX a este post :
Mas temos algoritmos de tempo subexponenciais para alguns problemas difíceis de NP.
fonte
Uma crença falsa que foi popularizada este ano e é contada muitas vezes quando se tenta explicar todo o problema de , já que é explicado como eficiente:PP≠ NP P
"Se , podemos resolver um grande número de problemas com eficiência. Caso contrário, não podemos"P= NP
Se o puder ser resolvido em então . Eu acho que ninguém pensaria em executar esse algoritmo.S ( n g o o g o L p l e X ) P = N P3 SA T O ( ngo o go l p l e x) P= NP
Se , ainda podemos ter um algoritmo para executado em , que é menor que para . A maioria das pessoas ficaria mais do que feliz em poder resolver o para 4 bilhões de cidades tão rapidamente.T S P n log ( log n ) n 5 n ≤ 2 32 T S PP≠ NP TSP nregistro( logn ) n5 n ≤ 232. TSP
fonte
Essa é realmente uma crença falsa na matemática, mas surge frequentemente nos contextos do TCS: se as variáveis aleatórias e são independentes, então, condicionadas a elas permanecem independentes. (falso, mesmo que seja independente de e ).Y Z Z X YX Y Z Z X Y
fonte
Computação distribuída = computação distribuída de alto desempenho (clusters, grades, nuvens, seti @ home, ...).
Algoritmos distribuídos = algoritmos para esses sistemas.
Spoiler: Se isso não parece muito com uma "crença falsa", sugiro que você dê uma olhada em conferências como PODC e DISC e veja que tipo de trabalho as pessoas estão realmente fazendo quando estudam aspectos teóricos da computação distribuída.
Uma configuração típica de problema é a seguinte: Temos um ciclo com nós; os nós são rotulados com identificadores exclusivos do conjunto ; os nós são determinísticos e trocam mensagens entre si de maneira síncrona. Quantas rodadas de comunicação síncrona (em função de ) são necessárias para encontrar um conjunto independente máximo? Quantas rodadas são necessárias para encontrar um conjunto independente com pelo menos nós? [A resposta para essas duas perguntas é exatamente , descoberta em 1986–2008.]{ 1 , 2 , . . . , poli ( n ) } n n / 1000 Θ ( log ∗ n )n { 1 , 2 , . . . , poli ( n ) } n n / 1000 Θ ( log∗n )
Ou seja, as pessoas geralmente estudam problemas que são completamente triviais da perspectiva de algoritmos centralizados e têm muito pouco em comum com qualquer tipo de supercomputação ou computação de alto desempenho. O ponto certamente não é acelerar a computação centralizada usando mais processadores, ou algo assim.
O objetivo é construir uma teoria da complexidade classificando problemas fundamentais de gráfico de acordo com sua complexidade computacional (por exemplo, quantas rodadas síncronas são necessárias; quantos bits são transmitidos). Problemas como conjuntos independentes em ciclos podem parecer inúteis, mas eles desempenham um papel semelhante ao 3-SAT na computação centralizada: um ponto de partida muito útil para as reduções. Para aplicações concretas do mundo real, faz mais sentido examinar dispositivos como roteadores e comutadores em redes de comunicação, em vez de computadores em grades e clusters.
Essa crença falsa não é totalmente inofensiva. Na verdade, torna bastante difícil vender trabalhos relacionados à teoria de algoritmos distribuídos para o público em geral do TCS. Recebi relatórios hilários de árbitros de conferências do TCS ...
fonte
Fundamental, mas comum quando lidamos pela primeira vez com notações assintóticas. Considere a seguinte "prova" da relação de recorrência e :T ( 1 ) = 1T( n ) = 2 T( n / 2 ) + O ( n logn ) T( 1 ) = 1
Provamos por indução. Para o caso base, vale para . Suponha que a relação seja válida para todos os números menores que ,nn = 1 n
QED (é?)
fonte
Até recentemente, eu pensava que toda máquina de Turing fita múltipla que é executada no tempo pode ser simulada por uma máquina de Turing inconsciente de duas fitas no tempo da seguinte maneira sentido:T ( n ) M o O ( T ( n ) log T ( n ) )M T( N ) Mo O ( T( N ) logT( N ) )
(veja este post do rjlipton, por exemplo)
Bem, a segunda linha não se mantém em geral, se . Precisamos de uma função de ordem totalmente construtível no tempo (consulte esta pergunta para a definição de funções (totalmente) construtíveis no tempo) ou precisamos permitir que execute infinitamente time (permitimos que seja executado após atingir o estado de aceitação no tempo ). O problema é que, para construtível pelo tempo geral , não podemos "medir" etapas no tempo menos que .Θ ( T ( n ) log T ( n ) ) M o M o O ( T ( n ) log T ( n ) ) T : N → N Θ ( T ( n ) log T ( nEXP- TEuME≠ NEXP- TEuME Θ(T(n)logT(n)) Mo Mo O(T(n)logT(n)) T:N→N O ( T ( n ) log T ( n ) ) E X P - T I M E = N E X P - T I M EΘ(T(n)logT(n)) O(T(n)logT(n)) EXP−TIME=NEXP−TIME
A prova desta afirmação é muito semelhante à prova a resposta da Q1 aqui , portanto, nós só vai dar as ideias-chave.
Tome um problema arbitrário , L ⊆ { 0 , 1 } ∗ . Então existe um k ∈ N , st L pode ser resolvido por um NDTM M em 2 n k etapas. Podemos supor que a cada passo M entre no máximo dois estados diferentes para simplificar. Em seguida, defina a função f ( n ) = { ( 8 n + 2L∈NEXP−TIME L⊆{0,1}∗ k∈N L M 2nk M
É possível provar quefé construtível no tempo.
Agora suponha que alguma máquina de Turing inconsciente funcione no tempo . Então g é totalmente construtível no tempo.g(n)=Θ(f(n)logf(n)) g
Agora, o seguinte algoritmo resolve :L
fonte
Aqui estão meus dois centavos:
Além disso, a máquina sempre para.
A definição está correta? (Não)
fonte
fonte
fonte
fonte