El teorema de la jerarquía del tiempo establece que las máquinas de Turing pueden resolver más problemas si tienen (suficiente) más tiempo. ¿Se mantiene de alguna manera si el espacio está limitado asintóticamente? ¿Cómo se relaciona DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n),...
Es bien sabido que el problema de detención es indiscutible. Sin embargo, es posible "comprimir" exponencialmente la información sobre el problema de detención, de modo que descomprimirla sea computable. Más precisamente, es posible calcular a partir de una descripción de máquinas de Turing y un...
Klop, van Oostrom y de Vrijer tienen un documento sobre el cálculo lambda con patrones. http://www.sciencedirect.com/science/article/pii/S0304397508000571 En cierto sentido, un patrón es un árbol de variables, aunque solo lo estoy considerando como una tupla anidada de variables, por ejemplo,...
En el Apéndice B de Impulso y privacidad diferencial de Dwork et al., Los autores declaran el siguiente resultado sin pruebas y se refieren a él como la desigualdad de Azuma: Supongamos que C1,…,CkC1,…,CkC_1, \dots, C_k sean variables aleatorias con valores reales de modo que para cada...
¿Quién fue la primera persona en mostrar que un idioma está en NP si se puede verificar un certificado para el idioma en tiempo polinómico? ¿Tenemos un documento que lo demuestre formalmente? ¿Cuándo comenzó la comunidad TCS a desestimar el no determinismo en favor de la verificabilidad? No puedo,...
Quiero ser muy específico ¿Alguien sabe de una prueba o prueba de la siguiente propuesta: ∃p∈Z[x],n,k,C∈N,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),\forall G, H \in STRUC[\Sigma_{graph}]...
Disculpas de antemano por esta una pregunta suave que no tiene una respuesta cerrada y correcta. Este es probablemente el mejor foro para hacer mi pregunta. Soy un estudiante graduado de tercer año en el grupo de teoría de una de las 15 escuelas más importantes de EE. UU. Hasta ahora, me ha ido...
Supongamos que se le da dos determinista empuje hacia abajo autómatas que reconocen las lenguas y B , y el deseo de determinar si hay un lenguaje regular R tal que A ⊆ R y R ∩ B = ∅ . Básicamente, el desafío es determinar si existe un DFA que pueda reconocer de cuál de los dos idiomas proviene una...
En la preimpresión reciente https://arxiv.org/abs/1801.00776 , se afirma que números reales se pueden ordenar en el tiempo O ( n √nnn y espacio lineal. El artículo parece razonable, aunque no soy un experto en algoritmos de clasificación.O(nlogn−−−−√),O(nlogn),O(n \sqrt{\log n}), Si es...
Hay investigadores que muestran que el bit de borrado tiene que consumir energía, ¿hay alguna investigación sobre el consumo promedio de energía del algoritmo con complejidad computacional ? Supongo que la complejidad computacional está correlacionada con el consumo promedio de energía, espero...
Imaginemos que tenemos dos conjuntos de puntos tamaño . ¿Cuál es la complejidad (temporal) de las pruebas si difieren solo por rotación? : existe una matriz de rotación tal que ?mmm O O T = O T O = I X = O YX,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^nOOT=OTO=IOOT=OTO=IOO^T=O^TO=IX=OYX=OYX=OY Hay un...
Recientemente intenté implementar Aaron's Cedille-Core , un lenguaje de programación minimalista capaz de probar teoremas matemáticos sobre sus propios términos. También probé la inducción de tipos de datos codificados con λ, lo que dejó en claro por qué serían necesarias sus extensiones. Menos...
¿Existe una máquina de Turing que pueda decidir si casi todas las demás máquinas de Turing se detienen? N→{Mi}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥⋅∥‖⋅‖\| \cdot \| f(i)=∥{n:Mi can't decide whether Mn halts}∥.f(i)=‖{n:Mi can't decide whether Mn halts}‖.f(i) = \|\{n: M_i \text{ can't decide whether...
Además de la academia, que es claramente el hogar de los teóricos, me pregunto acerca de los trabajos industriales relacionados con la informática teórica, los que exigen una base matemática pura. Salud
Considere una función calculada por un circuito booleano C con n entradas de tamaño s ( n ) = p o l y ( n ) sobre la base { X O R , A N D , N O T } (con grado 2 para la X O R , A N D puertas).FffCCCnortenns ( n ) = p o l y ( n )s(n)=poly(n)s(n) = \mathsf{poly}(n){ X O R , A N D , N O T...
Deje que sea un ciclo con cuatro vértices. Para un gráfico arbitrario con vértices y m aristas digamos , ¿cuántos existen? ¿Hay un límite inferior para esto?C4C4C_4GGGnnnm>nn−−√m>nnm>n\sqrt
Soy un estudiante graduado de tercer año en una universidad "top 20" que trabaja en la complejidad fina (mucho jugando con 3-SUM, OV y las conjeturas de dureza populares habituales). He sido bastante productivo durante el último año más o menos y tengo 3 documentos aceptados y dos presentados. Todo...
Es bien sabido que el complemento de tiene contexto. Pero, ¿qué pasa con el complemento de ?{ww∣w∈Σ∗}{ww∣w∈Σ∗}\{ ww \mid w\in \Sigma^*\}{www∣w∈Σ∗}{www∣w∈Σ∗}\{ www \mid w\in
Estoy leyendo la prueba desde aquí y me topé con un problema técnico (pero crucial). Sé que esto es bastante específico y el contexto es problemático, pero no pude resolverlo yo mismo. En las páginas 51 y 55, después de presentar los verificadores "estándar", se vuelven a modificar los...
Suponga que uno tiene un algoritmo aleatorio (BPP) usa bits de aleatoriedad. Las formas naturales de amplificar su probabilidad de éxito a , para cualquier elegido , sonAAArrr1−δ1−δ1-\deltaδ>0δ>0\delta>0 Ejecuciones independientes + voto mayoritario: ejecute independientemente veces, y...