¿Qué tan difícil es contar la cantidad de soluciones?
Una pregunta reciente de Huck Bennett sobre si la clase PH estaba contenida en la clase PP, recibió respuestas algo contradictorias (todo es cierto, parece). Por un lado, se dieron varios resultados de oráculo en sentido contrario, y por otro Scott sugirió que la respuesta es probablemente positiva...
Hay algunos problemas de conteo que implican contar exponencialmente muchas cosas (en relación con el tamaño de la entrada) y, sin embargo, tienen sorprendentes algoritmos deterministas exactos de tiempo polinómico. Ejemplos incluyen: Contar combinaciones perfectas en un gráfico plano (el...
Sabemos que el primer nivel de la jerarquía polinómica (es decir, NP y co-NP) está en PP, y que . También sabemos por el teorema de Toda que .PP⊆PSPACEPP⊆PSPACEPP \subseteq PSPACEPH⊆PPPPH⊆PPPPH \subseteq P^{PP} ¿Sabemos si ? Si no, ¿por qué es que con un oráculo de es más fuerte que ? ¿Es posible...
Dado un entero de longitud bits, ¿qué tan difícil es generar el número de factores primos (o alternativamente el número de factores) de ?NNNnnnNNN Si supiéramos la factorización principal de , entonces esto sería fácil. Sin embargo, si supiéramos el número de factores primos, o el número de...
Deje que denote un problema (decisión) en NP y deje que # X denote su versión de conteo.XXXXXX ¿En qué condiciones se sabe que "X es NP-completo" ⟹⟹\implies ¿"#X es # P-completo"? Por supuesto, la existencia de una reducción parsimoniosa es una de esas condiciones, pero esto es obvio y la única...
Arregle un entero nortenn alfabeto Σ = { 0 , 1 }Σ={0,1}\Sigma=\{0,1\} . Defina D FA ( n )DFA(n)DFA(n) como la colección de todos los autómatas de estado finito en nortenn estados con estado inicial 1. Estamos considerando todos los DFA (no solo los conectados, mínimos o no degenerados); por lo...
Supongamos que atenuamos el problema de contar las coloraciones adecuadas contando las coloraciones ponderadas de la siguiente manera: cada coloración adecuada obtiene el peso 1 y cada coloración incorrecta obtiene el peso donde es algo constante y es el número de aristas con puntos finales...
¿Cuáles serían las consecuencias de #P = FP? Me interesan las consecuencias prácticas y teóricas. Desde un punto de vista práctico, estoy particularmente interesado en las consecuencias sobre la Inteligencia Artificial. Punteros a papeles o libros son más que bienvenidos. Por favor no digas que...
Dado un gráfico no dirigido y no ponderado y un entero par , ¿cuál es la complejidad computacional de contar conjuntos de vértices tal que y el subgrafo de restringido al conjunto de vértices admite una combinación perfecta? ¿La complejidad # P-completa? ¿Hay alguna referencia para este problema?k...
Contar el número de coincidencias perfectas en un gráfico bipartito se puede reducir de inmediato a calcular el permanente. Dado que encontrar una coincidencia perfecta en un gráfico no bipartito está en NP, existe una reducción de los gráficos no bipartitos al permanente, pero puede implicar una...
¿Alguien puede sugerir una encuesta buena y reciente sobre problemas de conteo y / o problemas que son #P.
Supongamos que tenemos un problema parametrizado por un parámetro de valor real p que es "fácil" de resolver cuando y "difícil" cuando para algunos valores , . p = p 1 p 0 p 1p = p0 0p=p0p=p_0p = p1p=p1p=p_1pag0 0p0p_0pag1p1p_1 Un ejemplo es contar configuraciones de giro en gráficos. Contando los...
Recuerde que π(n)π(n)\pi(n) el número de primos ≤n≤n\le n es la función de recuento de primos . Por "PRIMES en P", calcular π(n)π(n)\pi(n) está en #P. ¿Es el problema # P-completo? O, tal vez, ¿hay una razón compleja para creer que este problema no es # P-completo? PD: Me doy cuenta de que esto...
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...
Deje ser una función de valor entero tal que esté en . ¿Se sigue que2 F # P F # PFFF2 F2F2F# P#P\#PFFF está en ? ¿Hay razones para creer que es poco probable que esto se cumpla siempre? ¿Alguna referencia que deba saber?# P#P\#P Sorprendentemente, esta situación surgió (con una constante mucho...
Supongamos que t(G)t(G)t(G) denota el número de árboles de expansión en un gráfico con vértices. Hay un algoritmo que calcula en operaciones aritméticas . Este algoritmo es para calcular , donde Q es el laplaciano de G y J es la matriz que consiste únicamente en 1 's. Para obtener más información...
¿Se ha trabajado en cómo la complejidad de las instancias aleatorias de # 2-SAT varía con la densidad de la cláusula? Es decir: ¿cómo varía la dificultad de contar soluciones satisfactorias para una instancia de 2-SAT generada aleatoriamente , a medida que varía la densidad de la cláusula? En...
¿Cómo puedo determinar la cantidad de rutas simples únicas dentro de un gráfico no dirigido? Ya sea para una determinada longitud o para un rango de longitudes aceptables. Recuerde que una ruta simple es una ruta sin ciclos, así que estoy hablando de contar el número de rutas sin...
Version corta. La prueba original de que # 2-SAT es # P- completo muestra, de hecho, que esas instancias de # 2-SAT son monótonas (no implican negaciones de ninguna variable) y bipartitas (el gráfico formado por las cláusulas sobre el variables es un gráfico bipartito) son #P -duro. Por lo tanto,...
Me han dicho que hay algunos buenos algoritmos de tiempo polinomiales para aproximar el número de rutas simples en un gráfico dirigido desde el vértice inicial dado hasta el vértice final dado . ¿Alguien sabe de una buena referencia sobre este tema?sssttt Antecedentes: contar el número exacto de...