Comencé a buscar estructuras de incidencia y diseños combinatorios (posible motivación: para enlazar algunas estructuras en el autoensamblaje generalizado), y el artículo de Wikipedia hace la siguiente declaración interesante pero inexplicable: los diseños de bloques tienen aplicación en las...
Supongamos que tienes hombres y mujeres. Cada persona tiene atributos. Cada persona indica un conjunto de atributos que debe tener un posible candidato. Una coincidencia es un conjunto de pares. Cada par une a un macho con una hembra. La satisfacción de una coincidencia es el número de atributos...
Problema de cláusulas independientes máximas parametrizadas : Entrada: Una fórmula F de r-CNFSAT que tiene n variables y cláusulas m , k Ques: ¿Existe al menos k cláusulas tales que sean mutuamente independientes, es decir, no se produce ninguna variable más de una vez en todas estas cláusulas...
Se sabe que si PAGS= NPAGSP=NPP=NP entonces Co NPAGS= PCPAGS[ O ( l o g( n ) ) , O ( 1 ) ]CoNP=PCP[O(log(n)),O(1)]CoNP= PCP[O(log(n)),O(1)] . Además, se sabe que nortemiXPAGS= PCPAGS[ p o l y( n ) , p o l y( n ) ]NEXP=PCP[poly(n),poly(n)]NEXP=PCP[poly(n),poly(n)]. Parece que el PCP no puede...
Se sabe que el problema # MONOTONE-2SAT es # P-completo. Esto significa que #SAT se puede reducir a eso. Mi pregunta es: dada una instancia #SAT , ¿cuál es la transformación que convierte F en su correspondiente instancia # MONOTONE-2SAT F ' ?FFFFFFF′F′F' Una segunda pregunta es: que es el número...
Encontré un artículo titulado " Factorizando enteros y calculando logaritmos discretos mediante aproximación diofantina " por CP Schnorr de 1993. Parece un método probabilístico con tiempo de ejecución polinomial esperado (y espacio) para realizar la factorización de enteros. Del documento: "Un...
He estado leyendo un artículo de un químico matemático. Propone algunos índices para medir la complejidad de las moléculas. De aquí en adelante, en lugar de moléculas, piense en gráficos conectados no dirigidos: un vértice es un átomo y un borde es un enlace entre los átomos. Es posible considerar...
Esta pregunta surge de una respuesta que Joe Fitzsimons dio a una pregunta diferente . La mayoría de las clases de complejidad natural tienen una "descripción intuitiva" de una línea que ayuda a caracterizar los problemas centrales de esa clase. NP es "verificación eficiente", #P se trata de...
Hace unos años, tomé una clase sobre teoría de la complejidad de Steven Rudich, y recuerdo que él dio una conferencia interesante que conecta las pruebas estadísticas (¡como se encuentra en los departamentos de estadística!) Con la complejidad del circuito. Lo recuerdo afirmando algo vagamente...
¿Se sabe si SPACE (n) (la clase de lenguajes reconocidos por TM deterministas con espacio lineal) es un subconjunto apropiado de E (la clase de lenguajes reconocidos por TM deterministas en el tiempo 2 ^ O
¿Alguien sabe de algún trabajo en la semántica de juegos para predicados coinductores? Un predicado coinductivo es aquel en el que el predicado en sí se llama en el cuerpo del predicado, y estamos tomando el significado del predicado como el mayor punto fijo de la definición subyacente. Dicho...
En el artículo Relativizaciones de la P =? Pregunta NP , Baker et al. demostró que existen mundos relativizados en los que se mantiene P = NP o P ≠ NP. Todos los oráculos en su configuración eran conjuntos recursivos. En otro artículo relativo a un Oráculo aleatorio , P A ≠ N P A ≠ co- N P A con...
(Estoy en el medio de mi primer curso cs teórico, así que me disculpo de antemano por lo que probablemente sea una pregunta estúpida). Entonces, decimos que algún lenguaje L está en P, lo que significa que se puede construir una máquina de Turing que genera un 1 si x está en L y 0 de lo contrario;...
Me gustaría verificar el estado del límite inferior del espacio para resolver el problema de conectividad en la transmisión en pases. El se indicó en la literatura, pero parece ser por un problema ligeramente diferente. ¿Me he perdido algo? Detalles abajo. Ω ( n / p )pagsppΩ ( n / p...
Un Quine es un programa de computadora que produce una copia de su propio código fuente como su única salida. ¿Hay algún programa de Quine que pueda imprimirse n veces, con n especificado de alguna manera en el
Supongamos que tenemos un multigraph (más tarde, un multihipegraph). Una camarilla de borde es un conjunto de bordes que se cruzan por pares (tienen al menos un vértice común). Entonces, cualquier camarilla de borde en un multigrafo siempre cae en una de dos categorías:CCC Una estrella : hay un...
Dado un torneo donde y haber dos acíclico sub-torneo de .S 1 S 2 TTTTS1S1S_1S2S2S_2TTT ¿Es NP-Complete el siguiente problema: Encontrar un sub-torneo acíclico máximo , que es un subconjunto de ?S 1 ∪ S 2SSSS1∪ S2S1∪S2S_1 \cup S_2 ¿Se puede resolver el problema dado en tiempo polinómico? De lo...
Tratar de encontrar la solución óptima para WEIGHTED-MAX-3SAT, la versión ponderada del problema de optimización 3-SAT, es NP-hard. De hecho, incluso aproximar la versión no ponderada de MAX-SAT arbitrariamente es probablemente NP-duro por el teorema de PCP. Un algoritmo canónico para aproximar...
Se necesita una referencia a las técnicas para demostrar que el tamaño de una brecha de integralidad está limitado por alguna expresión para un LP particular (o SDP, pero menos importante). También sería bueno tener una referencia a un lugar donde se describan técnicas para minimizar las brechas de...
Deseo saber la dimensión VC de un espacio de rango construido de la siguiente manera:(X,R)(X,R)(X,\mathcal{R}) XXX es el cilindro {(x,y,z)∈R3|x2+y2≤1}{(x,y,z)∈R3|x2+y2≤1}\{(x,y,z)\in\mathbb{R}^3|x^2+y^2\leq 1\} Los rangos en RR\mathcal{R} se forman tomando la unión de discos circulares de manera...