Mi pregunta hoy es (como siempre) un poco tonta; pero le pediría que lo considere amablemente. Quería saber sobre la génesis y / o motivación detrás del concepto de ancho de árbol. Estoy seguro de que entiendo que se usa en algoritmos FPT, pero no creo que esa sea la razón por la que se definió...
¿Cuáles son sus ejemplos favoritos donde la teoría de la información se usa para probar una declaración combinatoria ordenada de una manera simple? Algunos ejemplos que se me ocurren se relacionan con los límites para disminuir localmente códigos descifrables, por ejemplo, en este documento:...
Considere familias disjuntas de subconjuntos de {1,2, ..., n}, .tttF1,F2,…FtF1,F2,…Ft{\cal F}_1,{\cal F_2},\dots {\cal F_t} Suponer que (*) Para cada y cada , y , hay que contiene .i<j<ki<j<ki \lt j \lt kR∈FiR∈FiR \in {\cal F}_iT∈FkT∈FkT \in {\cal F}_kS∈FjS∈FjS \in {\cal...
Hablando informalmente, la complejidad de Kolmogorov de una cadena es la longitud de un programa más corto que genera x . Podemos definir una noción de 'cadena aleatoria' usándola ( x es aleatoria si K ( x ) ≥ 0.99 | x | ) Es fácil ver que la mayoría de las cadenas son aleatorias (no hay tantos...
Inspirado por esta pregunta y en particular el párrafo final de la respuesta de Or, tengo la siguiente pregunta: ¿Conoces alguna aplicación de la teoría de la representación del grupo simétrico en TCS? El grupo simétrico es el grupo de todas las permutaciones de con composición de operación de...
¿Cuáles son las aplicaciones de los códigos de corrección de errores en teoría además de la corrección de errores en sí? Conozco tres aplicaciones: el teorema de Goldreich-Levin sobre el bit de núcleo duro, la construcción del extractor de Trevisan y la amplificación de la dureza de la función...
Un gráfico es kkk elegible (también conocido como kkk -list-colorable ) si, para cada función FFf que asigna vértices a conjuntos de kkk colores, hay una asignación de color dodoc tal que, para todos los vértices vvv , c(v)∈f(v)c(v)∈f(v)c(v)\in f(v) , y tal que, para todos los bordes vwvwvw , c ( v...
El teorema de cuatro colores (4CT) establece que cada gráfico plano tiene cuatro colores. Hay dos pruebas dadas por [Appel, Haken 1976] y [Robertson, Sanders, Seymour, Thomas 1997]. Ambas pruebas son asistidas por computadora y bastante intimidantes. Hay varias conjeturas en la teoría de grafos...
Actualización : ahora se conoce el conjunto de obstrucciones (es decir, la "barrera" NxM entre los tamaños de cuadrícula colorable e incolorable) para todos los 4 colores sin rectángulo monocromático . ¿Alguien tiene ganas de probar 5 colores? ;) La siguiente pregunta surge de la teoría de...
Recientemente se hicieron dos preguntas en cs.se que estaban relacionadas o tenían un caso especial equivalente a la siguiente pregunta: Suponga que tiene una secuencia de números tales que Descomponerlo en la suma de dos permutaciones, y , de , de modo que . n ∑ n i = 1 a i = n ( n + 1 ) . π σ 1...
Los métodos polinómicos , por ejemplo, el teorema combinatorio de Nullstellensatz y Chevalley-Warning son herramientas poderosas en la combinatoria aditiva. Al representar un problema con los polinomios adecuados, pueden garantizar la existencia de una solución o el número de soluciones para los...
Tengo un interés creciente en la teoría de gráficos espectrales, lo cual me parece fascinante, y he comenzado a recopilar algunos documentos que aún no he leído más a fondo de lo que hasta ahora tengo. Sin embargo, tengo curiosidad acerca de una declaración que apareció en varias fuentes (por...
Nota: se trata del rompecabezas sudoku estándar de 9x9. La solución solo tiene que soportar acertijos legales resueltos . Por lo tanto, una solución no necesita admitir celdas vacías y puede confiar en las propiedades de un rompecabezas de sudoku resuelto. Me preguntaba esto, pero no podía pensar...
Hay varios algoritmos que deciden en tiempo polinómico si un gráfico se puede dibujar en el plano o no, incluso muchos con un tiempo de ejecución lineal. Sin embargo, no pude encontrar un algoritmo muy simple que uno pudiera explicar fácil y rápidamente en clase y mostrara que PLANARITY está en P....
El ISGCI enumera más de 1100 clases de gráficos. Para muchos de estos sabemos si el CONJUNTO INDEPENDIENTE se puede decidir en tiempo polinómico; a veces se denominan clases IS-easy . Me gustaría compilar una lista de clases máximas IS-easy. Estas clases juntas forman el límite de la trazabilidad...
Supongamos que es un gráfico con el número de colorante . Considere el siguiente juego entre Alice y Bob. En cada ronda, Alice elige un vértice y Bob responde con un color en para este vértice. El juego termina cuando se descubre un borde monocromático. Deje que sea la duración máxima del juego...
Para mi sorpresa, no pude encontrar documentos sobre esto, probablemente busqué las palabras clave incorrectas. Entonces, tenemos una variedad de cualquier cosa, y una función en sus índices; es una permutación.ffffff ¿Cómo reordenamos la matriz de acuerdo con con memoria y tiempo de ejecución...
Estoy buscando códigos de corrección de errores del siguiente tipo: códigos binarios con tasa constante, decodificable a partir de una fracción constante de errores, por un decodificador implementable como un circuito booleano de tamaño , donde es la longitud de codificación.O (...
En mi educación en ciencias de la computación, noto cada vez más que la mayoría de los problemas discretos son NP completos (al menos), mientras que la optimización de problemas continuos es casi siempre fácil de lograr, generalmente a través de técnicas de gradiente. ¿Hay excepciones a...
Dado un lenguaje regular (NFA, DFA, gramática o expresión regular), ¿cómo se puede contar el número de palabras aceptadas en un idioma determinado? Tanto "con exactamente n letras" como "con como máximo n letras" son de interés. Margareta Ackerman tiene dos documentos sobre el tema relacionado de...