Estoy tratando de entender lo que implica la investigación teórica en informática. ¿Qué hacen los informáticos teóricos? Sé que se dedica un tiempo considerable a la enseñanza, la supervisión de estudiantes graduados, la solicitud de financiación y las tareas departamentales. Dejándolos a un lado,...
Cruzado desde MO . Sea una clase gráfica definida por un número finito de subgrafías inducidas prohibidas, todas las cuales son cíclicas (contienen al menos un ciclo).CCC ¿Hay problemas de gráficos NP-hard que se puedan resolver en tiempo polinómico para no sean Clique y Clique cover?CCC Si...
GGGMGMGM_GGGGMG[i,j]MG[i,j]M_G[i, j]iiijjjGGG+++maxmax\max Digo que una subgrafía de (con el mismo conjunto de vértices) es sp-equivalente a si . En otras palabras, quitar bordes para ir de a no cambia la longitud de los caminos más cortos; los bordes eliminados no son necesarios para ninguna ruta...
Esto me confunde Un caso fácil de contar es cuando el problema de decisión está en y no hay soluciones.PPP Una conferencia muestra que el problema de contar el número de coincidencias perfectas en un gráfico bipartito (equivalentemente, contar el número de cubiertas de ciclo en un gráfico...
Estoy en posesión de un libro que, inspirado en los Principia Mathematica (PM) de Russell y el positivismo lógico, intenta formalizar un dominio específico determinando axiomas y deduciendo teoremas de ellos. En resumen, intenta hacer por su dominio lo que PM intentó hacer por las matemáticas. Al...
Hay una muy buena construcción por Conway de números surrealistas. Son "números" que contienen números reales y ordinales, están totalmente ordenados y tienen todas las propiedades de un campo (excepto que no forman un conjunto sino una clase). Vea, por ejemplo, este pdf o Wikipedia para una...
¿Se han implementado árboles de partición? Aquí, estoy hablando de los árboles de partición de la geometría computacional. Las primeras versiones (casi) óptimas de las cuales se debieron a Matousek y otros, y más recientemente a Timothy Chan: https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf Me...
¿Hay ejemplos concretos (o una rica fuente de) de aplicación de números adic en
¿Cuál es la relación entre el cálculo lambda simplemente escrito y la lógica de orden superior? Bajo Curry-Howard parece que el cálculo lambda simplemente escrito corresponde a la lógica proposicional. ¿Cómo se relaciona con la lógica de orden superior? Según este tutorial de Geuvers:...
Considere el siguiente problema: Dadas dos cadenas x, y, decida si existe un homomorfismo de cadena f tal que f (x) = y. Es fácil demostrar que este problema está en . ¿Hay otras cosas que podamos decir sobre este problema? por ejemplo, ¿está en , o incluso en ?NPNPNPcoNPcoNPcoNPPPP Este...
Como sabemos, la definición de la complejidad computacional del algoritmo es casi sin controversia, pero la definición de la complejidad computacional de los reales o los modelos de cálculo sobre los reales no es en tal caso. Conocemos el modelo y modelo de Blum y Smales en el libro Análisis...
Deje ser un campo. Como de costumbre, para una definimos como la complejidad lineal de sobre . Sea el conjunto de monomios de , es decir, los monomios que aparecen en con coeficiente distinto de cero.kkkf∈k[x1,x2,…,xn]f∈k[x1,x2,…,xn]f\in k[x_{1},x_{2},\ldots,x_{n}]L(f)L(f)L(f)fffkkkFFFffffff...
Supongamos que nuestra entrada es una binaria y tenemos que generar , donde es un número entero constante. Esto es solo un cambio si es una potencia de dos, pero ¿qué pasa con otros números? ¿Podemos hacerlo con un circuito de profundidad constante para cada ? ¿Qué pasa con ?⌊ x / c ⌋ c c c c =...
Considere la información completa de los juegos combinatorios de dos jugadores que terminan después de un número polinómico de movimientos, y de manera alterna, los jugadores eligen entre un número finito de movimientos permitidos. La pregunta habitual es cuán difícil es distinguir desde una...
Estoy considerando ideas sobre algoritmos cuánticos exactos. En particular, estoy considerando las posibles limitaciones de EQPEQP\mathsf{EQP} , que consiste en lenguajes exactamente decidibles por las familias de circuitos cuánticos uniformes de polimetro sobre un conjunto arbitrario de puerta...
Me gustaría saber (en relación con esta otra pregunta ) si se conocen límites inferiores para el siguiente problema de prueba: a uno se le da acceso de consulta a una secuencia de números no negativos y ε ∈ ( 0 , 1 ) , con la promesa de que ∑ n k = 1 a k = 1 o ∑ n k = 1 a k ≤ 1 - ε .unanorte≥ ⋯ ≥...
¿El problema de isomorfismo de semigrupo inverso finito es GI completo ? Aquí se supone que los semigrupos inversos finitos están dados por sus tablas de
La prueba de Goldreich et al. De que tres colorabilidad tiene cero pruebas de conocimiento utiliza un poco de compromiso para una coloración completa del gráfico en cada ronda [1]. Si un gráfico tiene vértices y bordes e , un hash seguro tiene b bits, y buscamos la probabilidad de error p , el...
Actualmente estoy escuchando la charla de Alan Kays "¿Es realmente complejo o simplemente lo complicamos?" ( https://www.youtube.com/watch?v=ubaX1Smg6pY&= ) donde dice que "los semáforos eran una mala idea y había algo llamado pseudo tiempo que era superior" (a las 51:40 en el video vinculado)....
Un árbol de decisión de lectura única se define de la siguiente manera: y F a l s e son árboles de decisión de una sola lectura.Tr u eTrueTrueFa l s eFalseFalse Si y B son árboles de decisión de lectura única yx es una variable que no ocurre en A y B , entonces ( x ∧ A ) ∨ ( ˉ x ∧ B ) también...