EDITAR EL 10/12/08:
Trataré de modificar la pregunta para que pueda interesar a más personas compartir sus opiniones. ¡NECESITAMOS sus contribuciones!
Esta publicación está inspirada en la de MO: ejemplos de creencias falsas comunes en matemáticas . Las listas grandes a veces generan una gran cantidad de respuestas cuyas cualidades son difíciles de controlar, pero después del éxito de la publicación relacionada en MO, estoy convencido de que sería útil enumerar un grupo de creencias falsas comunes en TCS.
Aún así, dado que el sitio está diseñado para responder preguntas de nivel de investigación, ejemplos como significa tiempo no polinómico no deberían estar en la lista. Mientras tanto, queremos algunos ejemplos que pueden no ser difíciles, pero sin pensar en detalles también parece razonable. Queremos que los ejemplos sean educativos, y generalmente aparecen cuando se estudia el tema por primera vez.
¿Cuáles son algunos ejemplos (no triviales) de creencias falsas comunes en informática teórica que les parecen a las personas que estudian en esta área?
Para ser precisos, queremos ejemplos diferentes de resultados sorprendentes y resultados contraintuitivos en TCS; Este tipo de resultados hace que las personas sean difíciles de creer, pero son VERDADEROS. Aquí estamos pidiendo ejemplos sorprendentes de que las personas puedan pensar que es cierto a primera vista, pero después de un pensamiento más profundo, la falla interna queda expuesta.
Como ejemplo de respuestas adecuadas en la lista, esta proviene del campo de los algoritmos y la teoría de gráficos:
Para un gráfico de nodos , un separador de bordes es un subconjunto de bordes de tamaño , donde los nodos de pueden dividirse en dos partes no adyacentes, cada una de las cuales consta de nodos como máximo . Tenemos el siguiente lema":G k S k G ∖ S 3 n / 4
Un árbol tiene un separador de 1 borde.
¿Derecho?
Respuestas:
Este es uno común a la geometría computacional, pero endémico en otros lugares: los algoritmos para la RAM real se pueden transferir a la RAM entera (para restricciones enteras del problema) sin pérdida de eficiencia. Un ejemplo canónico es la afirmación "La eliminación gaussiana se ejecuta en tiempo ". De hecho, las órdenes de eliminación descuidadas pueden producir enteros con exponencialmente muchos bits .O ( n3)
Peor aún, pero desafortunadamente común: los algoritmos para la RAM real con función de piso se pueden transferir a la RAM entera sin pérdida de eficiencia. De hecho, un piso real RAM + puede resolver cualquier problema en PSPACE o en #P en un número polinómico de pasos .
fuente
Acabo de descubrir otro mito, que es contribuido por la respuesta de @ XXYYXX a esta publicación :
Pero sí tenemos algoritmos de tiempo sub-exponenciales para algunos problemas NP-hard.
fuente
Una falsa creencia que se popularizó este año y se dice muchas veces cuando se trata de explicar todo el problema , ya que P se explica como eficiente:PAGS≠ NPAGS PAGS
"Si , entonces podemos resolver una gran cantidad de problemas de manera eficiente. Si no, no podemos"PAGS= NPAGS
Si puede ser resuelto en O ( n g o o g o l p l e x ) entonces P = N P . No creo que a nadie se le ocurra ejecutar este algoritmo.3 SA T O ( nsolo o golplex) P=NP
Si , todavía podemos tener un algoritmo para T S P que se ejecuta en n log ( log n ) , que es menor que n 5 para n ≤ 2 32 . La mayoría de la gente estaría más que feliz de poder resolver T S P para 4 mil millones de ciudades tan rápido.P≠NP TSP nlog(logn) n5 n≤232 TSP
fuente
Esto es realmente una falsa creencia en las matemáticas, pero surge a menudo en contextos de TCS: si las variables aleatorias e Y son independientes, entonces condicionadas por Z permanecen independientes. (falso incluso si Z es independiente de X e Y ).X Y Z Z X Y
fuente
Computación distribuida = computación distribuida de alto rendimiento (clusters, cuadrículas, nubes, seti @ home, ...).
Algoritmos distribuidos = algoritmos para estos sistemas.
Spoiler: Si esto no suena como una "falsa creencia", sugiero que eche un vistazo a conferencias como PODC y DISC, y vea qué tipo de trabajo están haciendo realmente las personas cuando estudian aspectos teóricos de la computación distribuida.
La configuración típica de un problema es la siguiente: tenemos un ciclo con nodos; los nodos se etiquetan con identificadores únicos del conjunto { 1 , 2 , . . . , poli ( n ) } ; los nodos son deterministas e intercambian mensajes entre sí de manera sincrónica. ¿Cuántas rondas de comunicación síncrona (en función de n ) se necesitan para encontrar un conjunto independiente máximo? ¿Cuántas rondas se necesitan para encontrar un conjunto independiente con al menos n / 1000 nodos? [La respuesta a estas dos preguntas es exactamente Θ ( log ∗n {1,2,...,poly(n)} n n/1000 , descubierto en 1986–2008.]Θ(log∗n )
Es decir, las personas a menudo estudian problemas que son completamente triviales desde la perspectiva de los algoritmos centralizados y que tienen muy poco en común con cualquier tipo de supercomputación o computación de alto rendimiento. El punto ciertamente no es acelerar la computación centralizada mediante el uso de más procesadores, ni nada de eso.
El objetivo es construir una teoría de la complejidad clasificando los problemas fundamentales de los gráficos de acuerdo con su complejidad computacional (por ejemplo, cuántas rondas sincrónicas se necesitan; cuántos bits se transmiten). Problemas como conjuntos independientes en ciclos pueden parecer inútiles, pero cumplen un papel similar al 3-SAT en la informática centralizada: un punto de partida muy útil en las reducciones. Para aplicaciones concretas del mundo real, tiene más sentido echar un vistazo a dispositivos como enrutadores y conmutadores en redes de comunicación, en lugar de computadoras en redes y clústeres.
Esta falsa creencia no es del todo inofensiva. En realidad, hace que sea bastante difícil vender trabajos relacionados con la teoría de algoritmos distribuidos a la audiencia general de TCS. He recibido divertidos informes de árbitros de las conferencias de TCS ...
fuente
Una primaria, pero común cuando tratamos por primera vez con anotaciones asintóticas. Considere la siguiente "prueba" de la relación de recurrencia y T ( 1 ) = 1 :T( n ) = 2 T( n / 2 ) + O ( n logn ) T( 1 ) = 1
Probamos por inducción. Para el caso base se cumple para . Suponga que la relación se cumple para todos los números menores que n ,n = 1 norte
QED (¿lo es?)
fuente
Hasta hace poco pensaba que todos los multi-cinta máquina de Turing que se ejecuta en el tiempo T ( n ) puede ser simulado por una de dos cintas ajeno Turing machinne M o en el tiempo O ( T ( n ) log T ( n ) ) en el siguiente sentido:METRO T( n ) METROo O ( T( n ) registroT( n ) )
(ver este post de rjlipton por ejemplo)
Bueno, la segunda línea no se sostiene en general, si . Necesitamos una función de orden completamente construible en el tiempo Θ ( T ( n ) log T ( n ) ) (vea esta pregunta para la definición de funciones (completamente) construibles en el tiempo) o necesitamos permitir que M o se ejecute por tiempo infinito (permitimos que M o se ejecute después de que alcanza el estado de aceptación enmiXPAGS- TyoMETROmi≠ NmiXPAGS- TyoMETROmi Θ ( T( n ) registroT( n ) ) METROo METROo tiempo). El problema es que para T : N → N construible en tiempo general,no podemos "medir" Θ ( T ( n ) log T ( n ) ) pasos en el tiempo O ( T ( n ) log T ( n ) ) a menos que E X P - T I M EO ( T( n ) registroT( n ) ) T: N → N Θ ( T( n ) registroT( n ) ) O ( T( n ) registroT( n ) ) .miXPAGS- TyoMETROmi= NmiXPAGS- TyoMETROmi
La prueba de esta afirmación es muy similar a la prueba en la respuesta de Q1 aquí , por lo tanto, solo daremos las ideas clave.
Tome un problema arbitrario , L ⊆ { 0 , 1 } ∗ . Entonces existe un k ∈ N , st L puede ser resuelto por un NDTM M en 2 n k pasos. Podemos suponer que en cada paso M entra como máximo en dos estados diferentes por simplicidad. A continuación, defina la función f ( n ) = { ( 8 n + 2L ∈ NmiXPAGS- TyoMETROmi L ⊆ { 0 , 1 }∗ k ∈ N L METRO 2nortek METRO
Se puede demostrar quefes construible en el tiempo.
Ahora suponga que una máquina de Turing ajena se ejecuta en el tiempo . Entonces g es completamente construible en el tiempo.sol( n ) = Θ ( f( n ) registroF( n ) ) sol
Ahora el siguiente algoritmo resuelve :L
fuente
Aquí están mis dos centavos:
Además, la máquina siempre se detiene.
¿Es correcta la definición? (No)
fuente
fuente
fuente
fuente