Coq, Agda e Idris tienen una jerarquía de tipos infinita (Tipo 1: Tipo 2: Tipo 3: ...). Pero, ¿por qué no hacerlo como λC, el sistema en el cubo lambda que está más cerca del cálculo de las construcciones, que tiene solo dos tipos, ∗∗* y , y estas reglas?◽◽◽ ∅ ⊢∗:◽∅⊢∗:◽\frac {} {∅ ⊢ * : ◽} Γ ⊢...
Estoy tratando de resolver un problema en particular, y pensé que podría resolverlo usando la teoría de autómatas. Me pregunto, ¿qué modelos de autómatas tienen una contención decidible en tiempo polinómico? es decir, si tiene máquinas , puede probar si eficiente. L ( M 1 ) ⊆ L ( M 2 )METRO1,...
Muchos problemas de gráficos duros se pueden resolver en tiempo polinómico en gráficos de ancho de árbol acotado . De hecho, los libros de texto suelen utilizar, por ejemplo, un conjunto independiente como ejemplo, que es un problema local . Aproximadamente, un problema local es un problema cuya...
Bueno, el título lo dice todo. La interesante pregunta anterior fue hecha por el comentarista Jay en mi blog (ver aquí y aquí ). Supongo que la respuesta es sí y que hay una prueba relativamente simple, pero no pude verlo de manera improvisada. (En términos muy generales, sin embargo, se podría...
Me gustaría saber si ha habido conjeturas que durante mucho tiempo no han sido probadas en TCS, que luego fueron probadas por una implicación de otro teorema, que pueden haber sido más fáciles de probar.
El ancho de árbol juega un papel importante en los algoritmos de FPT, en parte porque muchos problemas están parametrizados por FPT por el ancho de árbol. Una noción relacionada, más restringida, es la de ancho de ruta. Si un gráfico tiene un ancho de ruta , también tiene un ancho de árbol como...
Estoy interesado en el siguiente problema: Dada una matriz , ¿hay un gráfico no dirigido en n vértices cuya matriz de adyacencia al cuadrado es esa matriz?n×nn×nn\times nnnn ¿Se conoce la complejidad computacional de este problema? Observaciones: Por supuesto, esto también puede expresarse como...
En la descripción oficial del problema de Clay para P versus NP se afirma que se seguiría mostrando que "cada lenguaje en E [la clase de idiomas reconocibles en tiempo exponencial con una máquina de Turing determinista] puede ser calculado por una familia de circuitos booleanos < B n > tal...
Estoy interesado en aprender conexiones entre el "caos" o, más ampliamente, los sistemas dinámicos y la pregunta Aquí hay un ejemplo del tipo de literatura que estoy buscando:PAG= NPAGPAG=nortePAGP{=}NP Ercsey-Ravasz, Mária y Zoltán Toroczkai. "La dureza de la optimización como caos transitorio...
Es un resultado bien conocido que la pregunta ¿Una gramática libre de contexto genera un lenguaje regular? Es indecidible. Sin embargo, se vuelve decidible en un alfabeto unario, simplemente porque en este caso, las clases de lenguajes libres de contexto y regulares coinciden. Mi pregunta es...
¿Hay algún problema completo de NP sin un subconjunto infinito de instancias tal manera que la membresía en se pueda decidir en tiempo polinómico, y para todos , se pueda resolver en tiempo polinómico? (Suponiendo )Φ x ∈ Φ x P ≠ N PΦΦ\PhiΦΦ\Phix ∈ Φx∈Φx \in \PhiXxxPAG≠ NPAGP≠NPP \neq...
¿Existe algún proyecto en curso para verificar formalmente los teoremas y las pruebas de la teoría de la complejidad utilizando un asistente de pruebas como Coq? ¿Hay límites para hacer
Estoy resolviendo un problema que se afirma que es NP-hard en otro lugar, digamos en el artículo [XYZ]. La dureza NP proporcionada en [XYZ] es complicada y utiliza técnicas avanzadas. Después de un poco de investigación y trabajo, logré dar una prueba simple y clara de la dureza NP. Me pregunto si...
¿Existe un ejemplo explícito conocido de un algoritmo con la propiedad tal que si PAG≠ NPAGPAG≠nortePAGP\neq NP este algoritmo no se ejecuta en tiempo polinomial y si PAG= NPAGPAG=nortePAGP=NP se ejecuta en tiempo
Me doy cuenta de que esta podría ser una pregunta polémica, pero este parecía ser el lugar correcto para preguntar. Por favor, redirígeme si no. El trasfondo es que soy un "practicante" (estudiante de doctorado, no estudio teoría CS) pero tengo una base razonable en algoritmos de pregrado y...
La computación cuántica es un área activa de investigación que tiene como objetivo aprovechar la física cuántica (por ejemplo, entrelazamiento cuántico) para avanzar en las capacidades de eficiencia de las computadoras (no altera la tesis de Church-Turing ). ¿Cuáles son los experimentos más...
Suponga que se le da un gráfico H, simple, conectado y no dirigido. El problema del corte sin H se define de la siguiente manera: Dado un gráfico simple, no dirigido G, ¿hay un corte (partición de vértices en dos conjuntos no vacíos, L, R) de tal manera que los gráficos inducidos por los...
Por lo general, los algoritmos eficientes tienen un tiempo de ejecución polinómico y un espacio de solución exponencialmente grande. Esto significa que el problema debe ser fácil en dos sentidos: primero, el problema puede resolverse en un número polinómico de pasos y, en segundo lugar, el espacio...
Es bien sabido que el conjunto de lenguajes que tienen sistemas de prueba interactivos de dos probadores, en los que el verificador se ejecuta en tiempo polinómico (MIP), es NEXP. ¿Pero hay límites conocidos en el poder de tales pruebas interactivas cuando los probadores tienen un poder...
La dinámica de Glauber es una cadena de Markov en los colores de un gráfico en el que en cada paso se intenta cambiar el color de un vértice elegido aleatoriamente con un color aleatorio. No se mezcla para los 3 colores de un ciclo 5: hay 30 colores 3, pero solo se puede llegar a 15 de ellos...