Problemas fáciles con versiones de conteo difícil

20

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 $2$ -SAT y el número de clasificaciones topológicas.

¿Hay otras clases importantes (por ejemplo, ejemplos en celosías, árboles, teoría de números, etc.)? ¿Hay un compendio de tales problemas?

Hay muchos tipos de problemas en $P$ que tienen versiones de recuento duro $\#P$

¿Existe una versión de un problema natural en $P$ que se entienda más completamente o sea más simple que la coincidencia perfecta bipartita general (incluya detalles sobre por qué es más simple, como estar probablemente en las clases más bajas de la jerarquía $NC$ etc.) en alguna otra área (como la teoría de números, celosías) o al menos para gráficos bipartitos simples particulares, cuya versión de conteo es $\#P$ -duro?

Se apreciarán ejemplos de celosías, politopos, recuento de puntos, teoría de números .

reference-request counting-complexity nt.number-theory permanent decision-trees T ....
fuente

1

Presumiblemente quiere problemas naturales , ya que [por reducción de #SAT, problemas que # P-hard bajo [reducciones que multiplican la respuesta por un número distinto de cero] tienen problemas de decisión difíciles de HP] y [por la función de identidad, {x: x es 1+ (number_of_variables_ (

ϕ

$\phi$ )) unos o [un cero seguido de una asignación satisfactoria a

ϕ

$\phi$ ]} es # P-hard bajo el siguiente tipo de reducción más estricto, pero su versión de decisión es trivial].

@RickyDemer tu escritura es sucinta. Sí, quiero problemas naturales.

T ....

¿Realmente no entendemos completamente los emparejamientos perfectos en gráficos bipartitos? Además, hay un algoritmo RNC2 para el problema.

Sasho Nikolov

1

Si no lo hacemos. No tenemos un algoritmo determinista de

N C

$NC$

T ....

8

Aquí hay un excelente ejemplo (puedo estar sesgado).

Dado un conjunto parcialmente ordenado:
a) ¿tiene una extensión lineal (es decir, un orden total compatible con el orden parcial)? Trivial: Todos los posets tienen al menos una extensión lineal
b) ¿Cuántos tiene? # P-complete para determinar esto (Brightwell y Winkler, Counting Linear Extensions , Order, 1991)
c) ¿Podemos generarlos todos rápidamente? Sí, en tiempo amortizado constante (Pruesse y Ruskey, Generando Extensiones Lineales Rápidas , SIAM J Comp 1994)

Gara Pruesse
fuente

3

+1: Estoy de acuerdo en que es un excelente ejemplo (estaba pensando en publicarlo yo mismo y luego vi esta respuesta). Además, para que alguien diga "¿Qué hay de decidir si hay al menos otra extensión lineal?", Ese problema también es completamente trivial: un pedido total tiene 1 extensión, todos los demás posets tienen> 1. Y detectar exactamente 2 extensiones también es fácil (esto sucede si hay exactamente un par de elementos incomparables). De hecho, hay una clasificación completa de posets con hasta 7 extensiones lineales (ver Hanamura-Iwata, IPL 2011 ).

Joshua Grochow

Este es un buen ejemplo de hecho. Sin embargo, existe un problema mucho "más simple" que disfruta del mismo tipo de propiedades (más simple en el sentido de que estas propiedades son casi triviales de probar). Contando el número de asignaciones satisfactorias de un DNF: a) cada DNF no vacío es satisfactoria b) el conteo es # P-completo (reducción a #SAT) c) la enumeración se puede hacer con retraso polinómico (un tiempo amortizado tal vez constante, tener pensarlo)

holf

Me interesaría saber si se pueden generar asignaciones satisfactorias de DNF en tiempo amortizado constante (CAT). En ese momento y en mi trabajo con Frank, en 1994, las extensiones lineales eran el primer objeto "definido naturalmente" para el cual el conteo era difícil y la generación era lo más rápida posible, cuando se amortizaba (es decir, CAT). Las soluciones de DNF también parecen ser un candidato probable para esto. ¿Alguien tiene una referencia?

Gara Pruesse el

@GaraPruesse No tengo referencias para eso. Para monotono-DNF, es equivalente a enumerar un conjunto de hipergrafías de impacto y algunas técnicas para mejorar el retraso se presentan en "Algoritmos eficientes para dualizar hipergrafías a gran escala" de Keisuke Murakami y Takeaki Uno dl.acm.org/citation.cfm? id = 2611867 . Deberíamos comprobar si da CAT. Para DNF, mi intuición es que si hay una pequeña cláusula, entonces ya tienes suficientes soluciones para la fuerza bruta. De lo contrario, solo tiene cláusulas grandes y que son más propensas a chocar y que pueden usarse para diseñar un algoritmo CAT.

holf

17

Un ejemplo interesante de la teoría de números es expresar un número entero positivo como una suma de cuatro cuadrados. Esto se puede hacer de manera relativamente fácil en tiempo polinómico aleatorio (vea mi artículo de 1986 con Rabin en https://dx.doi.org/10.1002%2Fcpa.3160390713 ), y si recuerdo correctamente, ahora hay incluso un tiempo polinomial determinista solución. Pero contar el número de tales representaciones le permitiría calcular la función de suma de divisores , que es un tiempo polinómico aleatorio equivalente a factorizar . Entonces, el problema de contar es probablemente difícil. $\sigma(n)$ $n$

Jeffrey Shallit
fuente

"Entonces, el problema del conteo es probablemente difícil" ¿quieres decir probablemente

difícil? tienes evidencia?

# P

$\#P$

T ....

Por "probablemente difícil" quiero decir que es un tiempo polinómico aleatorio equivalente a la factorización de enteros.

Jeffrey Shallit

3

Entonces, para hacerlo explícito: el problema no es # P-hard (a menos que todo el infierno se desate).

Emil Jeřábek apoya a Monica el

@JeffreyShallit ¿Hay un ejemplo de

?

# P

$\#P$

T ....

Creo que el siguiente es un ejemplo aún más simple: "¿

tiene un divisor propio mayor que

" vs. "¿Cuántos divisores propios mayor que

tiene

?". La versión de decisión es equivalente a "

es compuesta", por lo que está en

, pero la versión de conteo no parece más fácil que factorizar.

n

$n$

1

$1$

1

$1$

n

$n$

n

$n$

P

$P$

Dan Brumleve

17

Un ejemplo muy agradable y simple de Graph Theory es contar el número de circuitos Eularian en un gráfico no dirigido.

La versión de decisión es fácil (... y el problema de los Siete Puentes de Königsberg no tiene solución :-)

La versión para contar es # P-hard: Graham R. Brightwell, Peter Winkler: Counting Eulerian Circuits es # P-Complete . ALENEX / ANALCO 2005: 259-262

Marzio De Biasi
fuente

Ese documento es "Nuestro enfoque es mostrar que, con la ayuda de un oráculo que cuenta los circuitos eulerianos, una máquina de Turing puede ... y" Deseamos calcular el número

de orientaciones eulerianas de

"salto de párrafo" Construimos para cualquier primo impar

, un gráfico

cuyo número de orbes es equivalente a

módulo

"y" Repetimos este proceso para cada primo p entre

y

, donde

, y ... "ciertamente sugieren que solo dan una reducción paralela, en lugar de incluso una

N

$N$

G

$G$

p

$p$

G_{p}

$G_p$

N

$N$

p

$p$

m

$m$

m^{2}

$m^2$

| E | = m

$|E| = m$

reducción de consulta.

m^{ϵ}

$m^{\epsilon}$

@MarzioDeBiasi es la decisión del circuito euleriano en Carolina del Norte?

T ....

1

@AJ. Solo necesita calcular la paridad del grado de cada nodo y verificar que estén todos pares. Parece definitivamente estar en Carolina del Norte.

Sasho Nikolov

44

Puede tomar la paridad de

bits utilizando una fórmula de tamaño

o un circuito de tamaño lineal de profundidad

. Entonces, si su gráfico se da como una matriz de adyacencia, calcule la paridad de cada fila, niegue y tome un AND. Y de

bits pueden ser realizadas con una fórmula de tamaño lineal, por lo general, se obtiene un

tamaño Boolean fórmula y un

tamaño del circuito booleano de profundidad

n

$n$

O (n^{2})

$O(n^2)$

O (\log n)

$O(\log n)$

n

$n$

O (n^{3})

$O(n^3)$

O (n^{2})

$O(n^2)$

O (\log n)

$O(\log n)$ (sobre la base AND-OR). Entonces, el problema está en

.

{N C}^{1}

$\mathsf{NC}^1$

Sasho Nikolov

2

De hecho, el problema está en

.

{A C}^{0} [2]

$\mathrm{AC}^0[2]$

Emil Jeřábek apoya a Monica el

6

Con respecto a su segunda pregunta, los problemas como Monotone-2-SAT (decidir la satisfacción de una fórmula CNF que tenga como máximo 2 literales positivos por cláusula) es completamente trivial (solo debe verificar si su fórmula está vacía o no) pero El problema de contar es # P-hard. Incluso aproximar el número de asignaciones satisfactorias de dicha fórmula es difícil (ver Sobre la dureza del razonamiento aproximado, Dan Roth, Inteligencia Artificial, 1996).

holf
fuente

5

De [Kayal, CCC 2009] : evaluación explícita de polinomios aniquiladores en algún momento

Del resumen: `` Este es el único problema computacional natural donde la determinación de la existencia de un objeto (el polinomio aniquilador en nuestro caso) se puede hacer de manera eficiente, pero el cálculo real del objeto es demostrablemente difícil ''.

$\mathbb{F}$ $\vec{f} = (f_1, ..., f_k)\in\mathbb{F}[x_1, ..., x_n]$ $k$ $d$ $n$ $\mathbb{F}.$ $\vec{f}$ $A$ $A(f_1, ..., f_k) = 0.$

$k$ $(f_1, ..., f_k)$ $k \ge n+1,$ $A$ $(f_1, ..., f_k)$

$p,$ $(f_1, ..., f_k)\in\mathbb{Z}[x_1, ..., x_n]$ $A(t_1, ..., t_k)\in\mathbb{Z}[t_1, ..., t_k],$ $A(0, ..., 0)\bmod{p}.$

ANNIHILATING-EVAL es -hard. Además, el polinomio aniquilador no tiene una representación de circuito pequeño a menos que colapse. $\#\mathsf{P}$ $A(t_1, ..., t_k)$ $\mathsf{PH}$

Daniel Apon
fuente

1

Al igual que para el ejemplo de Marzio, la prueba de la reclamación 15.2 de ese documento parece indicar que solo muestran dureza bajo reducciones paralelas, en lugar de incluso bajo reducciones de .

m^{ϵ}

$m^{\hspace{.02 in}\epsilon}$

1

Los recursos que puedo encontrar parecen estar en desacuerdo con las definiciones. Deje que AE sea el problema que discute su respuesta. (... continuación)

1

(continuación ...) No he tratado de trabajar con mayor precisión lo que la base de la clase que utilizan, pero sería muy sorprendido si su resultado fue mejor que # P = DLOGTIME-uniform TC . (... continuación)

(

$\big(\hspace{-0.07 in}$

^{0}

$^0$

)

$\hspace{-0.06 in}\big)$

^{| |}

$^{\hspace{-0.06 in}||\hspace{-0.06 in}}$

^{AE}

$^{\text{AE}}$

^{[\sqrt{n}]}

$^{\hspace{-0.05 in}[\sqrt{n}]}$

1

(continuación ...) Por lo que yo puedo ver, esto no se sigue que LWPP MP poli .

\subseteq

$\subseteq$

^{AE}

$^{\text{AE}}$

^{[\sqrt[3]{n}]}

$^{[\sqrt[3]{n}]}$

/

$\hspace{-0.06 in}\big/\hspace{-0.04 in}$

1

En términos más generales, es decir, para arbitraria (incluso menor que ), la decisión es fácil debido al criterio jacobiano, ¿verdad? (Tenga en cuenta que el criterio jacobiano solo funciona en la característica> ; en la característica positiva pequeña, hay un criterio jacobiano modificado debido a Mittman-Saxena-Scheiblechner , pero que aparentemente solo conduce a un algoritmo para la decisión ...)

k

$k$

n

$n$

m a x d e g f_{i}

$max deg f_i$

{N P}^{# P}

$\mathsf{NP}^{\mathsf{\# P}}$

Joshua Grochow

Problemas fáciles con versiones de conteo difícil

Respuestas: