Es bien sabido que para una clase de concepto con VC dimensión , es suficiente obtener ejemplos etiquetados para PAC learn . ¿No me queda claro si el algoritmo de aprendizaje PAC (que utiliza estas muestras) es correcto o incorrecto? En los libros de texto de Kearns y Vazirani, así como de Anthony...
Estoy interesado en el problema clásico INCLUSIÓN DE IDIOMAS REGULARES. Dada una expresión regular , denotamos por L ( E ) el lenguaje regular asociado a ella. (Las expresiones regulares están en un alfabeto fijo Σ , con la unión de operaciones, Kleene-star y concatenación).miEEL (...
¿Hay algo en la literatura cercano al siguiente problema: Dado un gráfico bipartito con bipartición equilibrada , ¿existe una coincidencia perfecta en manera que por cada 2 aristas , exista una arista o arista? (o ambos) en ?{ U , W } M G u 1 w 1 , u 2 w 2 ∈ M u 1 w 2 u 2 w 1...
El "nombre del juego de mayor número" le pide a dos jugadores que escriban un número en secreto, y el ganador es la persona que anotó el número mayor. El juego comúnmente permite a los jugadores escribir funciones evaluadas en un punto, por lo que también sería una cosa aceptable para...
El problema de representar las variables ligadas en la sintaxis, y en particular el de la sustitución para evitar la captura, es bien conocido y tiene una serie de soluciones: variables nombradas con equivalencia alfa, índices de Bruijn, anonimato local, conjuntos nominales, etc. Pero parece haber...
En la teoría de la complejidad, la definición de complejidad de tiempo y espacio hace referencia a una máquina universal de Turing: resp. la cantidad de pasos antes de detenerse y la cantidad de celdas en la cinta tocada. Dada la tesis de Church-Turing, también debería ser posible definir la...
Desde el teorema de la jerarquía espacial se sabe que si fff es construible en el espacio, entonces DSPACE ( 2f(n)2f(n)2f(n) ) no es igual a DSPACE ( f(n))f(n))f(n)) . Aquí, por DSPACE ( f(n))f(n))f(n)) me refiero a la clase de todos los problemas que se pueden resolver en el espacio f(n)f(n)f(n)...
He leído sobre la sustitución hereditaria del cálculo simple de Lambda y del marco lógico con términos y tipos distintos. Me pregunto, ¿hay algún ejemplo de sustitución hereditaria en un sistema de tipo dependiente con una jerarquía universal? es decir, donde
Los avances en la computación cuántica han llevado al desarrollo de nuevos algoritmos clásicos. Ejemplos recientes notables son los algoritmos de inspiración cuántica para el álgebra lineal: Un algoritmo clásico de inspiración cuántica para sistemas de recomendación. Algoritmos clásicos de...
Se dice que dos grupos (G,⋅)(G,⋅)(G,\cdot) y (H,×)(H,×)(H, \times) son isomórficos si existe un homomorfismo de GGG a HHH que es biyectivo. El problema del isomorfismo grupal es el siguiente: dados dos grupos, verifique si son isomorfos o no. Hay diferentes formas de ingresar un grupo, las dos más...
En el artículo de Stephen Cook sobre el problema P vs NP, [1] afirma lo siguiente [2]: Tesis de viabilidad: un problema natural tiene un algoritmo factible si tiene un algoritmo de tiempo polinómico. Mi pregunta es, ¿qué quiere decir exactamente él (o, en general, qué quiere decir uno) con "un...
¿Se puede generalizar la naturaleza de dividir y conquistar de la FFT a otras transformaciones (z Transformar, chirp, etc.) automáticamente? ¿Existe un algoritmo que tome una descripción de la transformación (no sé qué información sería necesaria) y puede producir una función rápida como...
Específicamente, solicito recursos para aprender sobre los sistemas de aprendizaje automático que pueden actualizar sus respectivas redes de creencias (o equivalentes) durante la operación. Incluso me he encontrado con algunos, aunque no pude marcarlos. Como puede imaginar, es un tema bastante...
El teorema de la zona dice que si apuñalamos una disposición de n líneas con otra línea, la complejidad total de su zona , el conjunto de todas las caras 0, 1 y 2 adyacentes a ella, es O (n). La constante real es algo así como 6n al menos como se indica en varios libros de texto, y la prueba es por...
Hay varias nociones diferentes (probablemente no equivalentes) de universalidad computacional (ver, por ejemplo, las últimas dos páginas de http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ) y no hay consenso entre expertos sobre las nociones más correctas (ver, por ejemplo,...
Deje ser un gráfico conectado no regular cuyo grado está acotado. Supongamos que cada nodo contiene un token único.G = ( V, E)G=(V,E)G= (V, E) ¿Quiero barajar uniformemente los tokens entre el gráfico usando solo intercambios locales (es decir, el intercambio de tokens entre dos nodos adyacentes)?...
La mayor parte de la literatura parece estar relacionada con máquinas con oráculos individuales para problemas específicos, sin embargo, parece haber algunos documentos que consideran máquinas con oráculos múltiples. ¿Existe un buen trabajo o tesis que proporcione una visión general de lo que se...
¿Qué evidencia hay de que ?c o R P≠ NPAGcoRP≠NPcoRP \neq NP es la clase de idiomas para los que existe una máquina de Turing probabililista que se ejecuta en tiempo polinómico y siempre responde Sí en una entrada que pertenece al idioma y responde No con probabilidad al menos la mitad de una...
¿Es posible (barra oblicua puede proporcionar un ejemplo) para reducir la complejidad computacional de un problema mediante el uso de un algoritmo paralelo que no requiere una serie de procesadores en relación con el tamaño de
Por BPP / lineal, me refiero a máquinas BPP con asesoramiento lineal, que cumple la promesa cuando se le da el consejo "correcto", y la desrandomización debería darnos, por ejemplo, un algoritmo P / lineal o (SUBEXP / lineal). Si usamos suposiciones no uniformes, creo que los resultados clásicos...