En la película Inception, Cobb le pide a Ariadne que le pida que diseñe un laberinto que le tome el doble de tiempo. Esto se presta a un problema generalizado en el que tenemos una situación en la que los recursos están limitados por una cierta cantidad y quien verifique que este problema se...
Sea un problema de gráfico NP-completo. Supongamos que X es solucionable en tiempo polinómico en gráficos de diámetro acotado. En otras palabras, parametrizado por diámetro está en XP. (Recordemos que un problema está en XP si se puede resolver en tiempo). ¿Esto implica la capacidad de solución en...
Deje que SAT sea el lenguaje de esas instancias de SAT que contienen variables , deje que -SAT sea el lenguaje de esas instancias de SAT en las que cada cláusula tiene a lo sumo literales, y deje que -SAT sea su intersección. Deje , donde el rango infimum abarca todos los algoritmos (máquinas...
¿Hay un resultado de imposibilidad condicional o la pregunta está completamente
El modelo estándar de física (el modelo matemático que predice el bosón de Higg) es, hasta donde yo entiendo, nuestro modelo más completo del universo. Es decir, es la mejor descripción del juego matemático que se juega para hacer predicciones sobre el resultado de los experimentos realizados en...
¿Es la complejidad de la comunicación (CC) el único enfoque conocido para los algoritmos de transmisión de límites inferiores? ¿Existen otras técnicas, incluso si los límites inferiores condicionales ? En general, ¿estamos satisfechos con el progreso logrado a través de CC? ¿O buscar técnicas...
\newcommand{\cc}[1]{\mathsf{#1}} ¿Se un teorema en las siguientes líneas: Si es un poco más grande que , entonces ?f ( n ) N T I M E ( g ) ∩ c o N T I M E ( g ) ≠ N T I M E ( f ) ∩ c o N T I M E ( f )sol( n )g(n)g(n)F( n )f(n)f(n)N T I M E (g) ∩ c o N T I M E ( g) ≠ N T I M E ( f) ∩ c o N T I M E (...
Encontré una presentación de Ryan O'Donnell sobre los principios de invariancia. Después de probar el teorema de Berry-Esseen, hay una diapositiva que analiza las extensiones del teorema y una que se menciona que hay una llamada "versión desaleatorizada": Si -nice (es decir, tiene un tercer...
Recuerdo haber leído una publicación de blog que mostraba dos versiones de la misma prueba, una escrita por un humano y la otra por una máquina, y les pedí a los lectores que dijeran cuál es cuál. Tratando de buscar en Google la publicación nuevamente, parece que no puedo encontrar las palabras...
Es común definir la completitud de con respecto a las reducciones de espacio de registro de muchos.PAGSPP Estoy buscando una clase de complejidad tal manera que haya problemas P- completos wrt muchas- C- reducciones.C⊆ LC⊆LC \subseteq \mathsf{L}PAGSP\mathsf{P}CCC ¿Cuál es la clase reducción...
En el documento 'Sobre la desaparición de los coeficientes de Kronecker' aquí en http://arxiv.org/pdf/1507.02955v1.pdf , se muestra que decidir positividad de los coeficientes de Konecker es en general NP difícil. Sin embargo, hay una advertencia que establece que solo se necesita positividad de...
En [1] se afirma que "Sigue siendo una pregunta abierta si cada función en tiene circuitos (aunque al menos se sabe que no todas las funciones tienen circuitos uniformes DLogTime )".T C 0 # P T C 0#P#P\#PTC0TC0TC^0#P#P\#PTC0TC0TC^0 TC0TC0TC^0 circuitos generados por las funciones DLogTime no...
¿Existe un algoritmo para verificar si una expresión regular de tamaño n coincide con una cadena de tamaño m , suponiendo un alfabeto de tamaño fijo si eso importa?O ( n + m )O(norte+metro)O(n+m)nortenortenmetrometrom El algoritmo estándar de NFA es peor de los casos. Groz y col. lograr tiempo...
nnnv1,…,vn∈RNv1,…,vn∈RNv_1,\dots,v_n\in\Bbb R^N∥vi∥22≤1‖vi‖22≤1\|v_i\|_2^2\leq1i∈{1,…,n}i∈{1,…,n}i\in\{1,\dots,n\}c∈Rc∈Rc\in\Bbb Rn,Nn,Nn,Nϵ∈{−1,+1}nϵ∈{−1,+1}n\epsilon\in\{-1,+1\}^n∥∥∑i=1nϵivi∥∥∞<c.‖∑i=1nϵivi‖∞<c.\Big\|\sum_{i=1}^n\epsilon_iv_i\Big\|_\infty0 donde falla la conjetura de...
Siempre me he preguntado si las pruebas en ciencias de la computación se considerarían pruebas suficientes de la propuesta si tuvieran que asumir leyes físicas. Por ejemplo, me pregunto qué pasaría si algún día alguien probara P! = NP bajo el supuesto de la segunda ley de la termodinámica....
¿Hay alguna complejidad de comunicación aleatorizada (no trivial) conocida con límites inferiores para problemas de brecha natural en los que las entradas 1 están linealmente lejos de las entradas 0? Es decir, funciones parciales tal que la distancia de Hamming entre cada ( x , y ) ∈ f - 1 ( 1 ) y...
M M E┌ M┐⌜M⌝\ulcorner M \urcornerMETROMMMETROMMmiE\mathsf E E ┌M┐ =βMETRO.E⌜M⌝=βM.\mathsf E \ulcorner M \urcorner =_\beta M. Hay una variedad de codificaciones como la de Kleene que usa números naturales y la codificación moderna más eficiente es una sintaxis de orden superior de Mogensen. Otra...
Según Handshaking Lemma: cualquier gráfico no dirigido que tenga un vértice cuyo grado sea un número impar debe tener algún otro vértice cuyo grado sea un número impar. Esta observación significa que si se nos da un gráfico y un vértice de grado impar, y se nos pide que encontremos algún otro...
La conjetura del isomorfismo de Berman y Hartmanis establece que todos los conjuntos completos de son polinomiales en el tiempo isomorfos entre sí. Esto significa que los completos de pueden reducirse eficazmente entre sí mediante bijecciones de tiempo polinómico computables e invertibles. La...
Estoy buscando más problemas en con límites inferiores de complejidad temporal clásica. Algunas personas podrían preguntarse cómo podría probar un límite tan bajo. Vea abajo.PPP Límites inferiores exponenciales: Reclamación: Si tiene un problema que es E X P T I M E -completo bajo reducciones...