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...
\newcommand{\symp}{\Bumpeq} Una relación de coherencia en un conjunto X es una relación reflexiva y simétrica. Un espacio de coherencia es un par (X, \ symp_X) , y un morfismo f: X \ a Y entre espacios de coherencia es una relación f \ subseteq X \ veces Y tal que para todos (x, y) \ en f y (x ',...
CMSOL está contando la lógica monádica de segundo orden, es decir, una lógica de gráficos donde el dominio es el conjunto de vértices y bordes, existen predicados para la adyacencia vértice-vértice y la incidencia de borde-vértice, hay cuantificación sobre bordes, vértices, conjuntos de bordes y...
Esto pretende ser una pregunta de seguimiento a la publicación anterior de Robin Kothari sobre los resultados de la dureza del tiempo polinomial . Específicamente, estoy interesado en ver algunas pruebas de dureza para problemas que se cree que tienen límites inferiores aproximadamente , y digo...
El título habla por sí mismo. Aquí están Akinator y 20Q . El principio de estos juegos es hacerle al usuario una serie de preguntas relacionadas con alguna entidad elegida por el usuario. Y luego descubre qué es esta entidad. El núcleo del algoritmo es encontrar la "pregunta más útil" en cada...
Hay 4 restricciones diferentes que podemos tener al definir Random K-SAT. 1) El número total de literales en una cláusula dada es exactamente K o como máximo K 2) Un literal dado se puede usar con o sin reemplazo en la misma cláusula (A o A o A) 3) Una variable dada se puede usar con o sin...
Me mudé a esta pregunta desde StackOverflow donde id obtuvo ninguna respuesta. Tuvimos una pregunta similar si JSON es regular : JSON y XML son llamados frecuentemente para ser lenguajes libres de contexto; ambos se especifican principalmente por una gramática formal en EBNF. Sin embargo, esto...
Es ampliamente conocido que las fórmulas CNF se pueden dividir aproximadamente en 2 clases amplias: aleatoria versus estructurada. Las fórmulas estructuradas de CNF, en oposición a las fórmulas aleatorias de CNF, exhiben algún tipo de orden, mostrando patrones que es poco probable que ocurran por...
Esta pregunta es similar a los problemas NP-hard en los árboles : Hay una gran cantidad de problemas NP-completos que son manejables en los coógrafos . ¿Hay algún problema conocido que permanezca NP-completo cuando se restrinja a los coógrafos? Para ser más precisos, estoy interesado en ejemplos...
Digamos que descubrimos civilizaciones alienígenas que pueden enviar y recibir mensajes utilizando un canal de comunicaciones digitales interestelar. (Digamos que usando ondas de radio moduladas, pulsos láser, reubicando estrellas en varias órbitas, ¿qué tiene usted?) Supongamos que hemos decidido...
¿Qué se sabe sobre el siguiente problema? Dada una colección de funciones , encuentre una subcolección más grande sujeta a la restricción que VC-Dimension para algún entero .f : { 0 , 1 } n → { 0 , 1 } S ⊆ C ( S ) ≤ k kCCCF: { 0 , 1 }norte→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\}S⊆...
Me gustaría escribir pruebas matemáticas con algún asistente de prueba. Todo se escribirá utilizando la lógica de primer orden (con igualdad) y la deducción natural. El fondo es la teoría de conjuntos (ZF). Por ejemplo, ¿cómo podría escribir la siguiente prueba? Axioma:∀ x ∀ y( x = y↔ ∀ z( z∈ x ↔...
Estoy buscando una buena referencia para los caminos más cortos del cuello de botella. Específicamente, dados los vértices syt en un gráfico no dirigido con pesos de arista, desea la ruta más corta de sa t, donde la longitud de una ruta es la arista máxima en esa ruta. Esto se puede resolver en el...
Sea X1, ... , xnortex1,…,xnx_1, \ldots, x_n puntos en el plano R2R2\mathbb{R}^2 . Considere una gráfica completa con los puntos como vértices y con pesos de arista de ∥ xyo- xj∥2‖xi−xj‖2\|x_i - x_j\|^2 . ¿Siempre puedes encontrar un corte de peso que sea al menos 2323\frac 2 3 del peso total? Si...
Considere el siguiente problema, Dado un conjunto de números positivos { a 1 , ... , a n } en el que k ≥ 3 es una constante, queremos dividir el conjunto en m subconjuntos de tamaño k para que el producto de la suma de cada subconjunto Está maximizado.n = k mn=kmn = k m{ a1, ... ,...
¿Hay una encuesta (de papel, capítulo de libro, tutorial, enlaces, ...) de la semántica de varias características del lenguaje de programación? Originalmente estaba abrumado por las características de D aquí http://www.digitalmars.com/d/2.0/comparison.html Me gustaría ver qué podría obtener de...
Hay varias nociones en competencia de un "gráfico disperso". Por ejemplo, un gráfico empotrable en la superficie podría considerarse escaso. O un gráfico con densidad de borde acotada. O un gráfico con gran circunferencia. Un gráfico con gran expansión. Un gráfico con ancho de árbol acotado....
En el algoritmo de cifrado minúsculo : Se usan diferentes múltiplos de una constante mágica para evitar ataques simples basados en la simetría de las rondas. La constante mágica, 2654435769 o 9E3779B9 16 se elige para ser , donde ϕ es la proporción áurea.232/ϕ232/ϕ2^{32}/ \phi ¿Qué...
Ya leí ejemplos de fórmulas en CTL pero no en LTL y viceversa, pero tengo problemas para comprender mentalmente las fórmulas de LTL y realmente cuál es, en el fondo, la
Estoy buscando lógicas modales, que están axiomatizadas por un conjunto finito de axiomas de profundidad de anidamiento modal uno, y cuyo problema de satisfacción / derivabilidad es poco probable que esté en PSPACE. Sin la restricción en la profundidad de anidamiento modal, esto no es un problema,...