Sea una fórmula booleana que consta de los operadores habituales AND, OR y NOT y algunas variables. Me gustaría contar el número de asignaciones para satisfacer B . Es decir, quiero encontrar el número de asignaciones diferentes de valores de verdad a las variables de para las cuales asume un valor...
Esta pregunta se migró de Stack Overflow porque se puede responder en Computer Science Stack Exchange. Migrado hace 7 años . Estoy un poco confundido por alguna terminología que he encontrado con respecto a la complejidad de los problemas de optimización. En una clase de...
Hace poco estuve leyendo sobre algoritmos para verificar la bimilaridad y leí que el problema es P-completo . Además, una consecuencia de esto es que este problema, o cualquier problema P-completo, es poco probable que tenga algoritmos paralelos eficientes. ¿Cuál es la intuición detrás de esta...
Esta pregunta se migró de Intercambio teórico de apilamiento de informática porque se puede responder en Intercambio apilado de informática. Migrado hace 7 años . En este artículo de Wikipedia sobre el problema de la camarilla en la teoría de grafos , establece al...
Estoy buscando algunas pistas en una pregunta que me hizo mi instructor. Así que descubrí que este problema de decisión es :NP-completeNP-complete\sf{NP\text{-}complete} En un gráfico , ¿hay un árbol de expansión en G que contenga un conjunto exacto de S = { x 1 , x 2 , ... , x n } como hojas. Me...
Supongamos que P≠NPP≠NP\mathsf{P} \neq \mathsf{NP} . NPINPI\mathsf{NPI} es la clase de problemas en NPNP\mathsf{NP} que no están ni en PP\mathsf{P} ni en NPNP\mathsf{NP} -duros. Puede encontrar una lista de problemas conjeturados como NPINPI\mathsf{NPI} aquí . El teorema de Ladner nos dice que si...
Me gustaría comenzar la pregunta diciendo que soy programador y que no tengo muchos antecedentes en teoría de la complejidad. Una cosa que he notado es que si bien muchos problemas son NP completos, cuando se extienden a problemas de optimización, algunos son mucho más difíciles de aproximar que...
Una posible motivación para estudiar las clases de complejidad computacional es comprender el poder de los diferentes tipos de recursos computacionales (aleatoriedad, no determinismo, efectos cuánticos, etc.). Si lo miramos desde esta perspectiva, parece que podemos obtener un axioma plausible para...
Aquí está el problema. Dado , donde cada T i ⊆ { 1 , ... , n } . ¿Hay un subconjunto S ⊆ { 1 , ... , n } con un tamaño máximo de k tal que S ∩ T i ≠ ∅ para todo i ? Estoy tratando de reducir este problema a SAT. Mi idea de una solución sería tener una variable x ik , n , T1, ... ,...
Entonces entiendo la idea de que el problema de decisión se define como ¿Existe una ruta P tal que el costo sea menor que C? y puede verificar fácilmente que esto sea cierto al verificar la ruta que recibe. Sin embargo, ¿qué pasa si no hay un camino que se ajuste a este criterio? ¿Cómo...
El problema de la suma de subconjuntos es un problema clásico de NP completo: Dada una lista de números y un objetivo k , ¿hay un subconjunto de números de LLLLkkkLLL que sume a ?kkk Un estudiante me preguntó si esta variante del problema llamado problema del "subconjunto de productos" es...
He tenido problemas para aceptar la visión teórica de la complejidad de "eficientemente resuelto por algoritmo paralelo" que es dada por la clase NC : NC es la clase de problemas que puede resolver un algoritmo paralelo en el tiempo O(logcn)O(logcn)O(\log^cn) en procesadores con...
Me encontré con las siguientes dudas sobre la complejidad de Towers of Hanoi , sobre las cuales quisiera sus comentarios. ¿Está en NP? Intento de respuesta: supongamos que Peggy (probador) resuelve el problema y lo envía a Victor (verificador). Víctor puede ver fácilmente que el estado final de...
Muchas veces, si las complejidades tienen constantes como 3n, descuidamos esta constante y decimos O (n) y no O (3n). No puedo entender cómo podemos descuidar un cambio tan triple. ¡Algo varía 3 veces más rápido que otro! ¿Por qué descuidamos este hecho?
Esto está inspirado en una pregunta de entrevista . Se nos da una matriz de enteros y tenemos que determinar si hay distintos manera quea1,…,ana1,…,ana_1, \dots, a_ni<j<ki<j<ki \lt j \lt k ak−aj=aj−aiak−aj=aj−aia_k - a_j = a_j - a_i k−j=j−ik−j=j−ik - j = j - i es decir, las...
¿Hay algún problema en que tenga algoritmos aleatorios que superen los límites inferiores en algoritmos deterministas? Más concretamente, ¿conocemos alguna para la cual \ mathsf {DTIME} (n ^ k) \ subsetneq \ mathsf {PTIME} (n ^ k) ? Aquí \ mathsf {PTIME} (f (n)) significa el conjunto de idiomas que...
¿Cómo puedo probar que la conversión de CNF a DNF es NP-Hard? No estoy pidiendo una respuesta, solo algunas sugerencias sobre cómo
Supongamos que tenemos un grafo dirigido y dos nodos y . Me gustaría saber si ya hay algoritmos para calcular el siguiente problema de decisión:G=(V,E)G=(V,E)G=(V,E)AAABBB ¿Hay al menos dos caminos entre y de la misma longitud?AAABBB ¿Qué tal la complejidad? ¿Puedo resolverlo en tiempo...
El logaritmo discreto es lo mismo que encontrar en , dada una , c , y N .bbbab=cmodNab=cmodNa^b=c \bmod NaaacccNNN Me pregunto en qué grupos de complejidad (por ejemplo, para computadoras clásicas y cuánticas) se encuentra, y qué enfoques (es decir, algoritmos) son los mejores para realizar esta...
Según Immerman , la clase de complejidad asociada con las consultas SQL es exactamente la clase de consultas seguras en Q ( F O ( C O U N T ) )Q(FO(COUNT))\mathsf{Q(FO(COUNT))} (consultas de primer orden más operador de conteo): SQL captura consultas seguras. (En otras palabras, todas las consultas...