Existe una gran literatura sobre "pruebas de propiedad": el problema de realizar una pequeña cantidad de consultas de recuadro negro a una función para distinguir entre dos casos:F: { 0 , 1 }norte→ RF:{0 0,1}norte→Rf\colon\{0,1\}^n \to R es miembro de alguna clase de funciones CFFfCC\mathcal{C}...
Wikipedia proporciona ejemplos de problemas donde la versión de conteo es difícil, mientras que la versión de decisión es fácil. Algunos de estos están contando combinaciones perfectas, contando el número de soluciones para 222 -SAT y el número de clasificaciones topológicas. ¿Hay otras clases...
Estoy buscando material tutorial que cubra las pruebas de corrección del compilador, preferiblemente utilizando métodos de denotación, al nivel de un estudiante graduado principiante. Alternativamente, ¿conoce algunos ejemplos simples de compiladores que pueda usar para ilustrar los problemas?...
Si bien el teorema de Adleman muestra que , no conozco ninguna literatura que investigue la posible inclusión de B Q P ⊆ P / poly . ¿Qué consecuencias teóricas de la complejidad tendría tal inclusión?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}BQP⊆P/polyBQP⊆P/poly\mathsf{BQP}...
Una cadena de suma es una secuencia de enteros positivos donde y cada índice , tenemos para algunos índices . La longitud de la cadena de adición es ; El objetivo de la cadena de suma es .x 1 = 1 i ≥ 2 x i = x j + x k 1 ≤ j , k < i n(x1,x2,…,xn)(x1,x2,…,xn)(x_1, x_2, \dots, x_n)x1=1x1=1x_1 =...
Un problema clásico en la teoría de la probabilidad es expresar la probabilidad de un evento en términos de eventos más específicos. En el caso más simple, se puede decir P[A∪B]=P[A]+P[B]−P[A∩B]P[A∪B]=P[A]+P[B]−P[A∩B]P[A \cup B] = P[A] + P[B] - P[A \cap B] . Escritura Vamos ABABAB para el evento...
Estoy buscando una buena encuesta sobre algoritmos y complejidad del álgebra lineal (operaciones como rango, inverso, valores propios, ... para matrices booleanas, y enteros / racionales) con énfasis en paralelo ( jerarquía ) y algoritmos polytime. No pude encontrar uno reciente....
En la clase de complejidad , se conjetura que algunos problemas NO están en la clase N C , es decir, problemas con algoritmos deterministas paralelos. El problema del flujo máximo es un ejemplo. Y se cree que hay problemas en N C , pero todavía no se encuentra una prueba.PAGP\mathsf{P}N...
¿Ha habido investigaciones sobre la implementación de construcciones de extractor de aleatoriedad? Parece que las pruebas de extractor utilizan Big-Oh, dejando la posibilidad de grandes constantes ocultas, lo que hace que las implementaciones programáticas sean potencialmente poco...
(Esta pregunta es un poco una "encuesta"). Actualmente estoy trabajando en un problema en el que trato de dividir los bordes de un torneo en dos conjuntos, los cuales son necesarios para cumplir con algunas propiedades estructurales. El problema "se siente" bastante difícil, y espero que sea...
Suponga que un gráfico con vértices se presenta como un flujo de bordes, pero se permiten múltiples pases sobre el flujo.n msolGGnortennmetromm Monika Rauch Henzinger, Prabhakar Raghavan y Sridar Rajagopalan observaron que el espacio es necesario para determinar si hay un camino entre dos vértices...
Tengo dos preguntas históricas: ¿Quién describió por primera vez el cálculo no determinista? Sé que Cook describió problemas NP-completos, y que Edmonds propuso que los algoritmos P son algoritmos "eficientes" o "buenos". Busqué en este artículo de Wikipedia y hojeé "Sobre la complejidad...
El siguiente problema interesante surgió en mi investigación recientemente: INSTANCIA: Gráfico .G ( V, E)G(V,E)G(V, E) SOLUCIÓN: Una finalización de ciclo impar sin acordes, definida como un superconjunto del conjunto de bordes E, de modo que el gráfico completado G ' ( V , E ' ) tiene la...
¿Cuáles son algunos resultados conocidos para encontrar una submatriz n-dimensional exacta dentro de una matriz n-dimensional? En 1D, es solo un problema de coincidencia de cadenas, KMP lo hace en tiempo lineal. En 2D, este documento muestra que se puede hacer en tiempo lineal con poco espacio...
Esta pregunta es similar a una pregunta más general sobre cuál es el modelo teórico correcto de una computadora para diseñar algoritmos y estructuras de datos. Aquí, pregunto específicamente sobre las computadoras actuales de alto rendimiento (como las que figuran como las 500 principales ) o...
En la computación cuántica adiabática (AQC), uno codifica la solución a un problema de optimización en el estado fundamental de un [problema] Hamiltoniano . Para llegar a este estado fundamental, comienza en un estado inicial (fundamental) fácilmente refrigerable con Hamiltoniano H i y "recocido"...
¿Hay alguna encuesta de algoritmos para calcular interpolantes? ¿Qué pasa con los documentos en un solo algoritmo? El caso que más me interesa es y , más la restricción de que el interpolante es lo más pequeño posible. (Conozco el artículo de McMillan de 2005 , que describe cómo obtener...
¡Predecir el mercado de valores es difícil! ¿Puede TCS hacer este sentimiento más formal? Recientemente comencé a pensar un poco sobre las finanzas y me preguntaba cómo podría ayudar el conocimiento de TCS. Los fondos de cobertura y las empresas de inversión parecen utilizar el comercio...
Pregunta principal / general Deja que LLL sea un idioma. Defina los idiomas LiLiL_i con L0=LL0=LL_0 = L y Li={xwy:xy∈Li−1,w∈L}Li={xwy:xy∈Li−1,w∈L}L_i = \{xwy : xy \in L_{i-1}, w \in L\} para i≥1i≥1i \geq 1 . Considere L = ⋃ L i . Por lo tanto, hacemos repetidamente "Insertar" L sobre sí misma...
¿Cuál es la complejidad del tiempo (no la complejidad de la consulta) del algoritmo de Grover? Me parece claro que es ya que hayΩ( √Ω ( log( N) N--√)Ω(log(N)N)\Omega(\log(N) \sqrt{N})iteraciones y cada iteración requiere el uso de la operación de reflexión que a su vez lleva tiempoΩ(log(N))usando...