¿Hay conjeturas en la informática teórica que impliquen algún parámetro n y se hayan probado para valores pequeños de n AND para números primos pero luego resultaron ser falsos? En teoría de números existen tales problemas, por ejemplo. como Aaron Meyerowitz señala el de los coeficientes de los...
Soy un estudiante graduado en matemáticas con una sólida formación en lógica. He tomado un curso de posgrado en lógica junto con cursos de posgrado sobre teoría de modelos finitos y otro sobre forzado y teoría de conjuntos. La mayoría de los textos de CS parecen asumir solo un trasfondo muy modesto...
Cualquier mónada también es un funtor aplicativo y cualquier funtor aplicativo es un ficticio. Además, cualquier comonad es un functor. ¿Existe un concepto similar entre comonads y functors, algo así como un co-aplicador y cuáles son sus
Considere una permutación σσ\sigma de [1..n][1..n][1..n] . Una inversión se define como un par (i,j)(i,j)(i, j) de índices tales que i<ji<ji < j y σ(i)>σ(j)σ(i)>σ(j)\sigma(i) > \sigma(j) . Defina AkAkA_k como el número de permutaciones de [1..n][1..n][1..n] con a lo sumo kkk...
La complejidad del circuito de profundidad limitada es una de las principales áreas de investigación dentro de la teoría de la complejidad del circuito. Este tema tiene su origen en resultados como "la función de paridad no está en AC0AC0AC^{0} " y "la función mod no es calculada por ", donde es la...
En el algoritmo de Strassen, para calcular el producto de dos matrices y , las matrices y se dividen en matrices de bloques y el algoritmo procede calcular recursivamente productos de matriz de matriz de bloques en lugar de productos de matriz de matriz de bloques ingenuos , es decir, si queremos ,...
Estoy buscando ejemplos naturales de algoritmos eficientes (es decir, en tiempo polinómico) st su corrección y eficiencia pueden demostrarse de manera constructiva (p. ej., en o ), peroPAGR APAGRUNPRAHUNHUNHA no se conoce ninguna prueba que utilice solo conceptos eficientes (es decir, no sabemos...
A partir de Curry-Howard-Lambek, ha habido una buena trinidad de teorías de tipos, lógicas y categorías. Tengo curiosidad por saber qué semántica categórica obtienes al agregar subtipos (coercitivos) a una teoría de tipos; parece que esto no se ha explorado mucho, si es que lo ha hecho. En...
Recientemente, me he encontrado con la siguiente variante de coloración de bordes. Dado un gráfico conectado no dirigido, encuentre una coloración de los bordes que use la cantidad máxima de colores al tiempo que satisface la restricción de que, para cada vértice , los bordes incidentes a usan...
Una cosa que las computadoras cuánticas pueden hacer (posiblemente incluso con solo circuitos cuánticos de profundidad logarítmica BPP +) es aproximar-muestrear la transformada de Fourier de una función de valor booleano en P.± 1±1\pm 1 Aquí y más abajo, cuando hablo de probar la transformada de...
Considere el siguiente problema QQQ : Se nos da un número entero , y k intervalos [ l i , r i ] con 1 ≤ l i ≤ r i ≤ 2 n . También se nos dan 2 n enteros d 1 , ... , d 2 n ≥ 0 . La tarea es seleccionar un número mínimo de intervalos [ l i , r i
Al tratar de convencer a los economistas de la relevancia de la teoría de la complejidad en forma impresa, ¿hay alguna referencia estándar para citar? Estoy familiarizado con la publicación del blog de Noam Nisan , la encuesta de Tim Roughgarden y el capítulo 11 del ensayo de Scott Aaronson . Estas...
¿Se conoce la siguiente clase de gráfico en la literatura? La clase de gráficos está parametrizada por los enteros positivos y y contiene cada gráfico modo que para cada vértice , el subgrafo de inducido en todos los vértices a distancia como máximo de en tiene un ancho de árbol como máximo...
Estoy haciendo una revisión de la literatura sobre el problema del isomorfismo gráfico. La mayoría de los trabajos que estoy leyendo están escritos por EM Luks y Laszlo Babai. Estos documentos utilizan el conocimiento de alto nivel de la teoría de grupos y la teoría de la complejidad. Como soy...
Actualmente soy un estudiante de secundaria, interesado en informática teórica y matemáticas aplicadas. Yo mismo me enseñé álgebra lineal y cálculo y matemáticas concretas. Tengo una noción ingenua de que para escribir mejores algoritmos, uno debe saber la mayor cantidad de matemáticas posible...
Parte del trabajo sobre la sensibilidad frente a la sensibilidad del bloque se ha dirigido a examinar funciones con un espacio lo más amplio posible entre y para resolver la conjetura de que solo es polinomialmente más grande que . ¿Qué pasa con la dirección opuesta? ¿Qué se sabe sobre las...
Supongamos que considero la siguiente variante de BPP, que nos permite llamar E (xact) BPP: un lenguaje está en EBPP si hay un TG polinomial aleatorio que acepta cada palabra del idioma con exactamente 3/4 de probabilidad y cada palabra no en el lenguaje con exactamente 1/4 de probabilidad....
Mientras buscaba en el Sistema de información sobre clases de gráficos y sus inclusiones , encontré varias clases de gráficos para las cuales el problema del Ciclo Hamiltoniano es NP completo, mientras que la complejidad de los problemas del Camino Hamiltoniano NO se conoce. Algunas de esas clases...
Siguiendo la sugerencia de Josh Grochow, estoy convirtiendo mi comentario de una pregunta anterior en una nueva pregunta. ¿Qué evidencia tenemos para ?U P ≠ N PUP≠NP\mathsf{UP} \neq \mathsf{NP} Aquí, U PUPAG\mathsf{UP} es la clase de lenguajes reconocibles por las máquinas de Turing no...
El límite inferior Blum 3n−o(n)3n−o(n)3n-o(n)es el límite inferior del circuito más conocido sobre la base completa de una función explícita f:{0,1}n→{0,1}f:{0,1}n→{0,1}f : \{0,1\}^n \to \{0,1\} , cf. La respuesta de Jukna a esta pregunta para obtener resultados relacionados. ¿Cuáles son los...