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,...
¿Es el siguiente problema en PTIME o coNP-hard: Dadas dos expresiones booleanas y e 2 en variables x 1 , ... , x n , sin negación (es decir, las expresiones se construyen completamente a través de ∧ y ∨ ). Decida si e 1 ≡ e 2 , es decir, tienen el mismo valor para todas las asignaciones a las...
Estoy interesado en ordenar una matriz de valores enteros positivos L=v1,…,vnL=v1,…,vnL = v_1, \ldots, v_n en tiempo lineal (en el modelo RAM con una medida de costo uniforme, es decir, los enteros pueden tener un tamaño logarítmico pero se supone que las operaciones aritméticas en ellos tomar...
Dadas dos matrices A y B , el problema de decidir si existe una matriz de permutación P tal que B = P - 1 A P es equivalente a (isomorfismo gráfico). Pero si relajamos P para que sea solo una matriz invertible, ¿cuál es la complejidad? ¿Existen otras restricciones en una matriz P invertible ,...
Dada una matriz m×nm×nm \times n (suponiendo que m≥nm≥nm \ge n ), ¿cuál es el algoritmo más rápido para calcular su rango y base de las columnas? Soy consciente de que se puede resolver a través de la intersección matroide lineal, lo que implica un algoritmo determinista de tiempo y un algoritmo...
¿Hay un algoritmo de tiempo aleatorio lineal en el lugar? Este es el algoritmo que algunas manos especialmente hábiles son capaces de realizar: dividir uniformemente una matriz de entrada de tamaño par y luego intercalar los elementos de las dos mitades. Mathworld tiene una breve página sobre...
El tiempo constante es la complejidad absoluta al final del tiempo. Uno puede preguntarse: ¿hay algo no trivial que se pueda calcular en tiempo constante? Si nos atenemos al modelo de máquina de Turing, entonces no se puede hacer mucho, ya que la respuesta solo puede depender de un segmento inicial...
Considere el problema # P-completo de contar el número de cubiertas de vértices de un gráfico dado G=(V,E)G=(V,E)G = (V, E) . Me gustaría saber si hay algún resultado que muestre cómo la dureza de dicho problema varía con algún parámetro de (por ejemplo, ).GGGd=|E||V|d=|E||V|d =...
Estoy buscando información sobre la complejidad computacional de la multiplicación de matrices de matrices rectangulares. Wikipedia afirma que la complejidad de multiplicar por B ∈ R n × p es O ( m n p ) (multiplicación del libro escolar).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times n}B∈Rn×pB∈Rn×pB \in...
¿Se conocen los resultados que descartan la existencia de estructuras de datos "demasiado buenas para ser verdaderas"? Por ejemplo: ¿se puede agregar la funcionalidad y J o i n a una estructura de datos de mantenimiento de pedidos (ver Dietz y Sleator STOC '87 ) y aún obtener operaciones de...
Hice una búsqueda sobre esto, pero no pude encontrar una respuesta de ninguna manera. Huck respondió por completo. Gracias
La eliminación gaussiana hace que el determinante de una matriz de tiempo polinómico sea computable. La reducción de la complejidad en la computación del determinante, que de otro modo es la suma de términos exponenciales, se debe a la presencia de signos negativos alternativos (la falta de lo que...
¿Conoce algún problema (preferiblemente al menos algo bien conocido), donde, para un tamaño de problema práctico , un algoritmo exponencial se ejecuta mucho más rápido que una contraparte de tiempo polinomial más conocida. Por ejemplo, suponga que un problema tiene un tamaño práctico * de y hay...
Decimos que una función es construible en el tiempo , si existe una máquina de Turing multi-cinta determinista M que en todas las entradas de longitud n realiza como máximo f ( n ) pasos y para cada n existe alguna entrada de longitud n en la que M realiza exactamente f ( n )
Es bien sabido que la complejidad de distinguir un moneda sesgada de una feria es θ ( ε - 2 ) . ¿Hay resultados para distinguir una moneda p de una moneda p + ϵ ? Puedo ver que para el caso especial de p = 0 , la complejidad será ϵ - 1 . Tengo el presentimiento de que la complejidad dependerá de si...
A lo que me refiero como contar es el problema que consiste en encontrar el número de soluciones para una función. Más precisamente, dada una función F: N→ { 0 , 1 }F:norte→{0 0,1}f:N\to \{0,1\} (no necesariamente caja negra), aproximada # { x ∈ N∣ f( x ) = 1 } = | F-...
¿Hay problemas decidibles de tal manera que para ningún algoritmo que resuelva el problema podamos dar un límite de tiempo en función de la longitud n de la instancia de entrada? Llegué a esta pregunta porque estaba pensando en lo siguiente: Supongamos que tenemos un problema recursivamente...
Considere el siguiente problema de prueba de membresía de subgrupo abelian . Entradas: Un grupo abeliano finito G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m} con arbitrariamente grande didid_i . Un generador de conjunto...
Arregle un problema de búsqueda NP-complete, por ejemplo, la forma de búsqueda de SAT. La búsqueda de Levin proporciona un algoritmo para resolver X que es óptimo en algún sentido. Específicamente, el algoritmo es "Ejecutar todos los posibles programas P en cola de milano en la entrada x , una vez...
Esta pregunta está inspirada en una pregunta existente sobre si una pila se puede simular usando dos colas en el tiempo amortizado por operación de pila. La respuesta parece ser desconocida. Aquí hay una pregunta más específica, correspondiente al caso especial en el que todas las operaciones PUSH...