Mientras leía el blog de Dick Lipton, me topé con el siguiente hecho cerca del final de su publicación de Bourne Factor : Si, por cada nnn , existe una relación de la forma (2n)!=∑k=0m−1akbckk(2n)!=∑k=0m−1akbkck (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} donde m=poly(n)m=poly(n)m = poly(n) , y...
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...
Tome un gráfico dirigido donde los bordes estén decorados con un número natural. Queremos el conjunto de todas las rutas entre dos vértices y modo que cada borde sucesivo en la ruta esté decorado con un número natural que sea mayor que el número natural que decora el borde
Sea un dígrafo (no necesariamente un DAG) y sea s , t ∈ V ( G ) . ¿Cuál es la complejidad de contar el número de rutas s - t simples en G ? GGGs,t∈V(G)s,t∈V(G)s,t \in V(G) s−ts−ts-tGGG Esperaría que el problema sea # completo pero no he podido localizar una referencia exacta. PP{\mathsf...
Introduciré mi problema con un ejemplo. Supongamos que está diseñando un examen, que consiste en un cierto conjunto de preguntas independientes (que los candidatos pueden obtener bien o mal) Desea decidir sobre un puntaje para dar a cada una de las preguntas, con la regla de que los candidatos con...
Se sabe que la intersección de tres matroides generales es NP-hard ( fuente ), que se realiza a través de la reducción del ciclo hamiltoniano. La reducción utiliza un matroide gráfico y dos matroides de conectividad. Un caso especial de un problema en el que estoy trabajando puede resolverse...
¿Qué debo leer para entender este problema? El poder de los circuitos cuánticos de pequeña profundidad. ¿Es ? En otras palabras, ¿se puede comprimir la parte "cuántica" de cualquier algoritmo cuántico a la profundidad de polylog (n), siempre que estemos dispuestos a realizar un posprocesamiento...
¿Está disponible públicamente el siguiente manuscrito? Dana Scott, 1969, Una teoría de funciones computables de tipo superior . Notas de seminario no publicadas, 7 páginas, Universidad de Oxford. Hay una discusión sobre este artículo en la sección 8.1.2, Tipos como conjuntos , en Cardone &...
Cualquier gráfico plano , respectivamente, externo-plano satisfaceG=(V,E)G=(V,E)G=(V,E)|E′|≤3|V′|−6|E′|≤3|V′|−6|E'|\le 3|V'|-6 , respectivamente, , para cada subgrafo G ′ = ( V ' , E ' ) de G . Además, las gráficas planas (externas) se pueden reconocer en tiempo...
Un gráfico mixto es un gráfico que puede tener bordes tanto dirigidos como no dirigidos. Su gráfico subyacente no dirigido se obtiene olvidando las orientaciones de los bordes dirigidos, y en la otra dirección se obtiene una orientación de un gráfico mixto al asignar una dirección a cada borde no...
Muchas publicaciones de ciencias de la computación de las décadas de 1950 y 1960 contienen especulaciones filosóficas fascinantes sobre la naturaleza de la mente y el significado de la información en relación con el mundo físico. Ejemplos famosos son la "Prueba de Turing", el "Espacio de cálculo"...
¿Existen ahora algoritmos / pruebas más simples para triangular un polígono plano en tiempo lineal? ¿Cuál es un buen recurso sobre el estado del arte de este famoso
Supongamos que denota el conjunto y C (n, k) denota el conjunto de todas las combinaciones de elementos de sin repetición. Supongamos que sea una -tupla en . Decimos que una permutación del conjunto evita si no hay k-tupla de enteros tal que [ n ][norte][n]k [ n ] p = p 1 p 2 . . . p k k C ( n...
Editar: como no he recibido ninguna respuesta / comentario en una semana, me gustaría agregar que estoy feliz de escuchar algo sobre el problema. No trabajo en el área, así que aunque sea una simple observación, puede que no lo sepa. ¡Incluso un comentario como "Trabajo en el área, pero no he visto...
Al leer el documento " Una teoría aplicativa para FPH " puede encontrar el siguiente pasaje: Considerando las teorías que caracterizan las clases de complejidad computacional, existen tres enfoques diferentes: en uno, las funciones que se pueden definir dentro de la teoría son...
Como todos saben, el famoso libro de Garey y Johnson (y muchos otros) proporciona una excelente referencia para la técnica de reducción en el entorno clásico. ¿Hay encuestas o libros sobre el tema de la técnica de reducción en algoritmos parametrizados, digamos la reducción de...
En realidad tengo dos preguntas: ¿Quién utilizó primero las relaciones lógicas para relacionar la semántica? Los rastreé hasta " La relación entre la semántica directa y de continuación " de Reynold , pero no puedo afirmar que haya hecho una búsqueda exhaustiva. He encontrado referencias a...
Uso el término del título en un sentido muy laxo. Hay una gran cantidad de trabajo sobre la teoría de los juegos evolutivos, incluidos sus fundamentos matemáticos. Me recomendaron "Juegos evolutivos y dinámica de población", pero aún no he profundizado en ello. También hay una gran cantidad de...
Esto está escrito en la entrada wiki de Ejecución simbólica , pero no puedo encontrar ninguna referencia para ello. ¿Alguien puede mostrarme un puntero?
Dados los conjuntos y , una relación difuncional entre ellos se define como una relación que satisface la siguiente propiedad:UNUNAsisiB ( ∼ ) ⊆ A × B(∼)⊆UN×si(\sim) \subseteq A \times B Si y y , entonces . a ∼ bun∼sia \sim bun′∼ b′un′∼si′a' \sim b'a ∼ b′un∼si′a \sim b'un′∼ bun′∼sia' \sim...