Para celebrar el cumpleaños número 100 de Alan Turing, quiero ver un documental sobre su vida. Sin embargo, hay varios documentales para elegir. ¿Qué documental sobre Alan Turing es tu favorito? Incluya solo un documental por
Me parece que los expertos en aprendizaje automático / minería de datos están familiarizados con P y NP, pero rara vez hablan de algunas de las clases de complejidad más sutiles (por ejemplo, NC, BPP o IP) y sus implicaciones para analizar los datos de manera efectiva. ¿Hay alguna encuesta de...
La fórmula más pequeña conocida para el determinante tiene un tamaño acuerdo con el folclore (o Ran Raz en su papel Las fórmulas multilineales para permanente y determinante son de tamaño superpolinomial ).norteO (logn )norteO(Iniciar sesiónnorte)n^{\mathcal O(\log n)} ¿Tienes alguna referencia...
La programación lineal es, por supuesto, hoy en día muy bien entendida. Tenemos mucho trabajo que caracteriza la estructura de soluciones factibles y la estructura de soluciones óptimas. Tenemos la fuerte dualidad, algoritmos de poli-tiempo, etc. Pero, ¿qué se sabe sobre las soluciones mínimas...
Hice esta pregunta hace unas semanas en mathoverflow , pero no obtuve respuesta. Aquí, por rejilla 3D de longitud de lado me refiero a la gráfica G = ( V , E ) con V = { 1 , ... , k } 3 y E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | a - x | + | b - y | + |
TC0TC0\mathsf{TC^0} dTC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd La entrada del zoológico para TC0TC0\mathsf{TC^0} solo menciona la separación entre la profundidad 2 y 3. ¿También hay una referencia estándar para el hecho de que la jerarquía AC0dACd0\mathsf{AC^0_d} no...
CMSOL está contando la lógica monádica de segundo orden, es decir, una lógica de gráficos donde el dominio es el conjunto de vértices y bordes, existen predicados para la adyacencia vértice-vértice y la incidencia de borde-vértice, hay cuantificación sobre bordes, vértices, conjuntos de bordes y...
¿Qué se sabe sobre el siguiente problema? Dada una colección de funciones , encuentre una subcolección más grande sujeta a la restricción que VC-Dimension para algún entero .f : { 0 , 1 } n → { 0 , 1 } S ⊆ C ( S ) ≤ k kCCCF: { 0 , 1 }norte→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\}S⊆...
Estoy buscando una buena referencia para los caminos más cortos del cuello de botella. Específicamente, dados los vértices syt en un gráfico no dirigido con pesos de arista, desea la ruta más corta de sa t, donde la longitud de una ruta es la arista máxima en esa ruta. Esto se puede resolver en el...
Estoy tratando de entender a qué clase de complejidad pertenece el siguiente problema: Problema de raíz polinómica exponencial (EPRP) Sea un polinomio con deg ( p ) ≥ 0 con coeficientes extraídos de un campo finito G F ( q ) con q un número primo y r una raíz primitiva para ese campo. Determine...
Si es un gráfico con el máximo grado 3 y es un menor de H , entonces es un menor topológica de .solGGHHHHsolGGHHH Wikipedia cita este resultado de la "teoría de grafos" de Diestel. Está listado como la Proposición 1.7.4 en la última versión del libro. El libro carece de prueba o cita. ¿Se conoce...
Leí el artículo de Freyd "Algebraically Complete Categories" en el famoso Como90 y tengo dos preguntas sobre la noción de compacidad algebraica que definió en ese artículo. (Si no está familiarizado con la definición, aquí está: una categoría se llama algebraicamente compacta si cada endofunctor...
en 1979 Hopcroft / Ullman escribió que L ⊆ P ⊆ NP ⊆ PSpace es conocido, pero L ⊊ PSpace es la única contención adecuada (y trivial) conocida, aunque se conjetura que todas son contenciones adecuadas, y "donde las cosas siguen en pie" ~ 4 décadas después . desde entonces, ¿hay alguna conexión...
El SAT único es el problema bien conocido: dada una fórmula CNF , ¿es cierto que F tiene exactamente un modelo?FFFFFF Estoy interesado en el problema «Exactamente -SAT»: dada una fórmula F de CNF y un entero m > 1 , ¿es cierto que F tiene exactamente m modelos?mmmFFFm>1m>1m>1FFFmmm Ambos...
Los idiomas Dyck se definen mediante la siguiente gramática S → S SDyck(k)Dyck(k)\mathsf{Dyck}(k) sobre el conjunto de símbolos { ( 1 , ... , ( k , ) 1 , ... , ) k } . Intuitivamente, los idiomas Dyck son los idiomas de paréntesis equilibrados de k tipos diferentes. Por ejemplo,...
Actualmente estoy haciendo una investigación de lenguaje formal que involucra clases de idiomas por encima de Regular pero debajo de Context Free. Estoy viendo cosas como máquinas multicontadores limitados por inversión, máquinas de contador de una sola pila, CFL deterministas, etc. Me pregunto si...
Por lo tanto, una búsqueda rápida en la web me llevó a creer que "APXHardness implica que no existe QPTAS para un problema a menos que [alguna clase de complejidad] esté incluida en alguna [otra clase de complejidad]" y ¡también es bien conocido! Parece que todo el mundo lo sabe, excepto yo....
Dada compuesto N∈NN∈NN\in\Bbb N tamiz campo de número general es mejor algoritmo de factorización conocida para la factorización de enteros de NNN . Es un algoritmo aleatorio y obtenemos una complejidad esperada de
El algoritmo simplex a menudo se trata dentro de la aritmética real o en el mundo discreto con cálculos exactos. Sin embargo, parece implementarse con mayor frecuencia con aritmética de punto flotante. Esto lleva a la pregunta de si el algoritmo simplex debe considerarse como un algoritmo...
Espero que alguien sepa algo sobre esto, así que no tengo que leer la literatura ... Considere una secuencia de números . Piense en la secuencia como n - 1 intervalos [ x 1 , x 2 ] , [ x 2 , x 3 ] , … , [ x n - 1 , x n ] . Claramente, la secuencia original es bitónica si algún punto en la línea...