Trabajar directamente con la complejidad del tiempo o los límites inferiores del circuito es aterrador. Por lo tanto, desarrollamos herramientas como la complejidad de la consulta (o la complejidad del árbol de decisiones) para manejar los límites inferiores. Dado que cada consulta toma al menos un...
Nunca antes había visto un algoritmo con un registro en el denominador, y me pregunto si hay algún algoritmo realmente útil con este formulario. Entiendo muchas cosas que podrían hacer que un factor de registro se multiplique en el tiempo de ejecución, por ejemplo, algoritmos de clasificación o...
Estoy interesado en una función booleana explícita con la siguiente propiedad: si es constante en algún subespacio afín de , entonces la dimensión de este subespacio es .f:0,1n→0,1f:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}fff0,1n0,1n\\{0,1\\}^no(n)o(n)o(n) No es difícil demostrar que una...
La teoría de categorías y el álgebra abstracta tratan la forma en que las funciones se pueden combinar con otras funciones. La teoría de la complejidad trata de cuán difícil es calcular una función. Es extraño para mí que no haya visto a nadie combinar estos campos de estudio, ya que parecen pares...
En la descripción oficial del problema de Clay para P versus NP se afirma que se seguiría mostrando que "cada lenguaje en E [la clase de idiomas reconocibles en tiempo exponencial con una máquina de Turing determinista] puede ser calculado por una familia de circuitos booleanos < B n > tal...
Me gustaría aprender sobre la Complejidad Parametrizada (tanto en el lado algorítmico como en el lado de la dureza). ¿Qué libros / apuntes puedo leer sobre este
¿Cómo puedo determinar la cantidad de rutas simples únicas dentro de un gráfico no dirigido? Ya sea para una determinada longitud o para un rango de longitudes aceptables. Recuerde que una ruta simple es una ruta sin ciclos, así que estoy hablando de contar el número de rutas sin...
El ancho de árbol juega un papel importante en los algoritmos de FPT, en parte porque muchos problemas están parametrizados por FPT por el ancho de árbol. Una noción relacionada, más restringida, es la de ancho de ruta. Si un gráfico tiene un ancho de ruta , también tiene un ancho de árbol como...
¿Todas las funciones cuyo peso de Fourier se concentra en los conjuntos de tamaño pequeño (o términos con bajo grado) se calculan mediante circuitos
¿Cuál es la complejidad (en la RAM entera estándar) de calcular la transformada discreta estándar de Fourier de un vector de enteros?nnn El algoritmo clásico para transformaciones rápidas de Fourier , atribuidas inapropiadamente [1] a Cooley y Tukey, generalmente se describe como funcionando en...
Supongamos que es un árbol de grado constante cuya estructura no conocemos. El problema es generar el árbol haciendo preguntas de la forma: "¿El nodo encuentra en la ruta del nodo al nodo ?". Suponga que cada consulta puede ser respondida en tiempo constante por un oráculo. Conocemos el valor de ,...
¿Se ha trabajado en cómo la complejidad de las instancias aleatorias de # 2-SAT varía con la densidad de la cláusula? Es decir: ¿cómo varía la dificultad de contar soluciones satisfactorias para una instancia de 2-SAT generada aleatoriamente , a medida que varía la densidad de la cláusula? En...
Estoy tratando de resolver un problema en particular, y pensé que podría resolverlo usando la teoría de autómatas. Me pregunto, ¿qué modelos de autómatas tienen una contención decidible en tiempo polinómico? es decir, si tiene máquinas , puede probar si eficiente. L ( M 1 ) ⊆ L ( M 2 )METRO1,...
Creo que un teorema de jerarquía de tamaño para la complejidad del circuito puede ser un gran avance en el área. ¿Es un enfoque interesante para la separación de clases? La motivación para la pregunta es que tenemos que decir hay alguna función que no puede calcularse mediante circuitos de...
¿Existe algún proyecto en curso para verificar formalmente los teoremas y las pruebas de la teoría de la complejidad utilizando un asistente de pruebas como Coq? ¿Hay límites para hacer
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
EDITAR (22 de agosto de 2011): Estoy simplificando aún más la pregunta y generando una recompensa por la pregunta. Quizás esta pregunta más simple tenga una respuesta fácil. También voy a tachar todas las partes de la pregunta original que ya no son relevantes. (¡Gracias a Stasys Jukna y Ryan...
Considere el lenguaje consiste en todas las cadenas -letter sobre modo que no haya dos letras iguales: k ΣLk−distinctLk−distinctL_{k-distinct}kkkΣΣ\Sigma Lk−distinct:={w=σ1σ2...σk∣∀i∈[k]:σi∈Σ and ∀j≠i:σj≠σi}Lk−distinct:={w=σ1σ2...σk∣∀i∈[k]:σi∈Σ and ∀j≠i:σj≠σi} L_{k-distinct} :=\{w =...
Rompecabezas Dado que el problema es largo aquí hay un caso especial que captura su sentido. Problema: Sea A un algoritmo detrminístico para 3-SAT. Es el problema de simular completamente el algoritmo A (en cada instancia del problema). P-Space duro? (Más precisamente, ¿hay razones para creer...
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...