Cuando se establece la conjetura o P ≠ N P (por ejemplo, por el Clay Mathematical Institute de S. Cook, ver aquí ) ¿qué sistema axiomático matemático se supone?P=NPP=NP\mathbf{P} = \mathbf{NP}P≠NPP≠NP\mathbf{P} \neq \mathbf{NP} Para probar o refutar tales afirmaciones, debe asumir algunos axiomas....
¿Cuáles son los ejemplos de problemas conocidos en (resp. ) que no se sabe que están en ni en ?M A N P B P PAMAM\mathsf{AM}MAMA\mathsf{MA}NPNP\mathsf{NP}BPPBPP\mathsf{BPP} Para , conozco los siguientes dos ejemplos:AMAM\mathsf{AM} No isomorfismo gráfico: dados dos gráficos etiquetados y , ¿son...
Dada una tabla de datos que contiene un número muy grande de filas, con cada fila que contiene un gran número k de campos, con cada campo que contiene un número grande pero fijo de bits, existen varios métodos para construir una estructura de "índice". que las operaciones siguientes se pueden...
He estado mirando una lógica modal con el axioma (◊A∧◊B)→◊((A∧◊B)∨(A∧B)∨(A∧◊B))(◊A∧◊B)→◊((A∧◊B)∨(A∧B)∨(A∧◊B)) (\Diamond A \land \Diamond B) \to \Diamond((A \land \Diamond B) \vee (A \land B) \vee (A \land \Diamond B)) Aproximadamente, esto dice que la relación de accesibilidad es lineal....
Supongamos que tiene varios conjuntos de enteros ( ) y desea calcular las intersecciones de algunos de ellos ( podría ser una consulta, pero desea admitir muchas de esas consultas , o tal vez incluso todas las consultas posibles)S1, S2. . . SnorteS1,S2...SnorteS_1, S_2 ... S_n∩ S1, S3, S7...
Tengo un conjunto de agentes y un conjunto de n tareas, y necesito asignar a cada agente exactamente una tarea de manera que se minimice el costo. Algunos agentes son incompatibles con algunas tareas.nortenortennortenorten Tengo una implementación del algoritmo húngaro que tarda aproximadamente un...
El problema de máxima satisfacción (Max-Sat) es el problema de encontrar el número máximo de cláusulas que se pueden satisfacer en una instancia de satisfacción booleana. El problema exacto 1 en 2 Sat pregunta, dado un conjunto de cláusulas cada una con dos literales, ¿hay un conjunto de literales...
Dado un número algebraico , estoy interesado en encontrar una aproximación de ℜ ( e α ) hasta una precisión dada, donde ℜ ( ) se refiere a la parte real del número complejo.αα\alphaR ( eα)ℜ(eα)\Re(e^\alpha)R ( )ℜ()\Re() Formalmente, quiero calcular un número racional tal que | ℜ ( e α ) - r | ≤...
La mayoría de los recursos con respecto a las nociones categóricas en la programación describen mónadas, pero nunca he visto una descripción categórica de los transformadores de mónadas. ¿Cómo podrían describirse los transformadores de mónada en los términos de la teoría de categorías? En...
Cuando intentamos construir un algoritmo para un nuevo problema, dividir y conquistar (usando la recursividad) es uno de los primeros enfoques que intentamos. Pero en algunos casos, este enfoque parece infructuoso ya que el problema se vuelve mucho más complicado a medida que crece su aporte. Mi...
¿Hay alguna semántica categórica para las lógicas no monotónicas? Parece que la respuesta simple a esto es "No" ya que la noción obvia de composición falla para cualquier modelo de lógica no monotónica. Pero, ¿hay un modelo que realmente funcione con una noción de composición adecuadamente...
Mi pregunta se refiere a la prueba del principal teorema de Ajtai en su innovador artículo de 1996, Generando instancias difíciles de problemas de red , lo que indica una conexión entre los problemas de red dura de peor caso y de media. Esta prueba me es difícil de entender. ¿Existe una exposición...
Existen bastantes teoremas, principalmente en teoría de grafos y optimización combinatoria, que a menudo se denominan buenas caracterizaciones. Por lo general, colocan una propiedad en , al mostrar que una propiedad se mantiene o hay algún obstáculo bien identificado que impide que se mantenga. A...
De acuerdo con el Módulo XOR Satisfiability Solver para la integración DPLL por Tero Laitinen, necesitamos cláusulas CNF para convertir una cláusula XOR-SAT literal si no queremos aumentar el número de literales. Entonces, entiendo que el costo computacional para convertir una expresión XOR-SAT en...
He estado trabajando en un proyecto independiente centrado en autómatas celulares y me preguntaba si esto podría ser algo que podría continuar en la escuela de posgrado en algún lugar. He visto algunos departamentos de matemáticas con dinámicas simbólicas, así como algunos departamentos de CS con...
Suponga que para un problema de minimización dado con solo soluciones enteras, es difícil decidir si la solución óptima es 5 o 6. Es decir, un algoritmo de tiempo polinomial con una relación de aproximación mejor que 6/5 implicaría .nortePAGSnortePAGSNPPAGS= NPAGSPAGS=nortePAGSP=NP 1) ¿Esto...
Un gráfico es localmente bipartito si la vecindad abierta de cada vértice induce un gráfico bipartito. (Según las búsquedas, el mismo nombre podría usarse para otra cosa relacionada con las superficies). ¿Qué problemas de NP-hard para gráficos generales se convierten en polinomios para gráficos...
Me parece que la tarea de eliminación de cuadrados se puede reducir a la tarea de factorización , pero que no hay forma de reducir la factorización a la eliminación de cuadrados. ¿Hay alguna manera de hacer que este "sentimiento" sea más preciso, es decir, alguna hipótesis comúnmente creída que se...
Para las complejidades de Kolmogorov inducida por lenguajes de descripción esencialmente óptimos, ¿existe un entero c tal que para todos los enteros positivos n , exista una cadena x tal queKK\hspace{.02 in}KCccnnnxxxn<K(x)<n+cn<K(x)<n+c\;\;\; n \: < \: K(x) \: < \: n\hspace{-0.04...
Vi este problema: Se dice que una secuencia no creciente de enteros positivos es n-realizable si el conjunto puede dividirse en subconjuntos mutuamente disjuntos tal que para cada .m1,m2,...,mkm1,m2,...,mkm_1,m_2,..., m_kIn={1,2,...,n}In={1,2,...,n}I_n=\{1,2,...,