Recientemente descubrí un límite inferior cuadrático en la complejidad de un problema en el modelo de árbol de decisión, y me pregunto si este resultado podría generalizarse parcialmente al modelo de máquina de acceso aleatorio. Por parcial , me refiero a una generalización de los programas de RAM...
Al leer el documento " Una teoría aplicativa para FPH " puede encontrar el siguiente pasaje: Considerando las teorías que caracterizan las clases de complejidad computacional, existen tres enfoques diferentes: en uno, las funciones que se pueden definir dentro de la teoría son...
Supongamos que estamos tratando con un lenguaje de programación que admite tipos lineales (los términos de tipo lineal se pueden usar como máximo una vez, por así decirlo). Esto permite tratar algunos efectos computacionales (como la mutación, incluso cambiar el tipo de operando) de una manera que...
Como todos saben, el famoso libro de Garey y Johnson (y muchos otros) proporciona una excelente referencia para la técnica de reducción en el entorno clásico. ¿Hay encuestas o libros sobre el tema de la técnica de reducción en algoritmos parametrizados, digamos la reducción de...
Hace un tiempo hice esta pregunta sobre Stack Overflow: Problema: la venta de Bob . Alguien sugirió publicar la pregunta aquí también. Alguien ya ha hecho una pregunta relacionada con este problema aquí: peso mínimo por debajo del bosque de la cardinalidad dada , pero, por lo que entiendo, no me...
Dada una matriz m×nm×nm \times n (suponiendo que m≥nm≥nm \ge n ), ¿cuál es el algoritmo más rápido para calcular su rango y base de las columnas? Soy consciente de que se puede resolver a través de la intersección matroide lineal, lo que implica un algoritmo determinista de tiempo y un algoritmo...
Estoy buscando documentos y artículos sobre lógicas subestructurales modales, no sobre la semántica de las modalidades de lógica lineal, sino sobre lógicas subestructurales aumentadas con operadores modales estándar, por ejemplo, K estructural (algo así como MALL con operador de caja, necesidad y...
El teorema del punto fijo de Banach dice que si tenemos un espacio métrico completo no vacío , entonces cualquier función uniformemente contractiva tiene un punto fijo único . Sin embargo, la prueba de este teorema requiere el axioma de elección: debemos elegir un elemento arbitrario para comenzar...
¿Cuáles son buenos documentos / libros para comprender mejor el poder de la descomposición modular y sus propiedades? Estoy particularmente interesado en los aspectos algorítmicos de la descomposición modular. He oído que es posible encontrar una descomposición modular de un gráfico en tiempo...
Un conjunto de bateo de una familia S= { S1, ... , Snorte}S={S1,...,Snorte}\mathcal{S} = \{S_1, \dots, S_n\} es un subconjunto HHH de ⋃nortei = 1Syo⋃yo=1norteSyo\bigcup_{i=1}^{n} S_i tal que H∩ Syo≠ ∅H∩Syo≠∅H \cap S_i \ne \emptyset para 1 ≤ i ≤ n1≤yo≤norte1 \le i \le n . El problema para encontrar...
La altura de estrella (generalizada) de un idioma es la anidación mínima de estrellas de Kleene requerida para representar el idioma mediante una expresión regular extendida. Recuerde que una expresión regular extendida sobre un alfabeto finito AAA satisface lo siguiente: (1) ∅,1∅,1\emptyset, 1 y...
Estoy tratando de entender algunos conceptos sobre la descomposición modular y los gráficos de ancho de camarilla. En este documento ("En gráficos P4-tidy"), hay una prueba de cómo resolver problemas de optimización como el número de camarilla o el número cromático usando la descomposición...
La desfuncionalización es una transformación de programa que convierte los programas de orden superior en programas de primer orden. La idea es que, dado un programa, solo hay finitamente muchas abstracciones lambda, por lo que puede reemplazar cada lambda con un id, y cada aplicación de función...
Antecedentes Las funciones en son PAC que se pueden aprender en tiempo cuasipolinomial con un algoritmo clásico que requiere consultas elegidas al azar para aprender un circuito de profundidad d [1]. Si no hay un algoritmo de factorización , entonces esto es óptimo [2]. Por supuesto, en una...
¿Puede indicar cómo construir la función Ackerman (en realidad estoy interesado en una versión propuesta por Rózsa Péter y Raphael Robinson) a través de operadores mu-recursivos estándar? Probé documentos originales de Péter y Robinson, pero el papel de Péter usa un idioma diferente al inglés y los...
En realidad tengo dos preguntas: ¿Quién utilizó primero las relaciones lógicas para relacionar la semántica? Los rastreé hasta " La relación entre la semántica directa y de continuación " de Reynold , pero no puedo afirmar que haya hecho una búsqueda exhaustiva. He encontrado referencias a...
Uso el término del título en un sentido muy laxo. Hay una gran cantidad de trabajo sobre la teoría de los juegos evolutivos, incluidos sus fundamentos matemáticos. Me recomendaron "Juegos evolutivos y dinámica de población", pero aún no he profundizado en ello. También hay una gran cantidad de...
Se sabe a través del teorema de aproximación universal que una red neuronal con incluso una sola capa oculta y una función de activación arbitraria puede aproximarse a cualquier función continua. ¿Qué otros modelos hay que también son aproximadores de función
Una categoría tiene biproductos cuando los mismos objetos son tanto productos como coproductos. ¿Alguien ha investigado la teoría de la prueba de categorías con biproductos? Quizás el ejemplo más conocido es la categoría de espacios vectoriales, en la que la suma directa y las construcciones de...
El problema de mantenimiento de la orden (o "mantener el orden en una lista") es apoyar las operaciones: singleton: crea una lista con un elemento, le devuelve un puntero insertAfter: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo...