División por dos de funciones en #P

Deje ser una función de valor entero tal que esté en . ¿Se sigue que $F$ $2F$ $\#P$ $F$ está en ? ¿Hay razones para creer que es poco probable que esto se cumpla siempre? ¿Alguna referencia que deba saber? $\#P$

Sorprendentemente, esta situación surgió (con una constante mucho mayor), para una función para la cual $F$ $F \in? \#P$ es un viejo problema abierto.

Nota: Conozco el artículo M. Ogiwara, L. Hemachandra, Una teoría de la complejidad para las propiedades de cierre factibles donde se ha estudiado un problema relacionado de división por 2 (ver Thm 3.13). Sin embargo, su problema es diferente, ya que definen la división para todas las funciones a través del operador de piso. Eso les permitió hacer algunas reducciones rápidas a los problemas de paridad.

cc.complexity-theory complexity-classes counting-complexity Igor Pak
fuente

@Kaveh: Si es una función , y una función de tiempo múltiple, entonces está en , pero no necesariamente (presumiblemente). Por ejemplo, no parece haber ninguna razón por la cual todas las funciones GapP no negativas deberían estar en , pero de esta manera son reducibles a .

f (x)

$f(x)$

# P

$\#P$

g (y)

$g(y)$

f (g (y))

$f(g(y))$

# P

$\#P$

g (f (x))

$g(f(x))$

# P

$\#P$

# P

$\#P$

Emil Jeřábek apoya a Monica el

@JoshuaGrochow: Sí, es "Aceptar si y solo si adivinó a los dos testigos 2F en orden lexicográfico".

@JoshuaGrochow Si hace una división sin función de piso,

colapsa a la siguiente clase de complejidad, que acabo de definir, a través del Teorema 5.9 en el libro TCTC.

hay un predicado de tiempo polinomial P y un polinomio q tal que, para todo

P P

${\bf PP}$

U P P X = {L |

${\bf UPPX} = \{ L |$

x

$x$

1.

$\bf 1.$

x \notin L \Rightarrow | | {y |

$x \not \in L \Rightarrow ||\{y|$

Entonces uno necesita mostrar dóndepertenece

en la jerarquía de complejidad. Es de esperar que

| y | \leq q (| x |) \land P (x, y)} | | < 1

$|y|\leq q(|x|) \wedge P(x,y)\}|| < 1$

2.

$\bf 2.$

x \in L \Rightarrow | | {y |

$x \in L \Rightarrow ||\{y|$

| y | \leq q (| x |) \land P (x, y)} | | \geq 1

$|y|\leq q(|x|) \wedge P(x,y)\}|| \geq 1$

}

$\}$

U P P X

${\bf UPPX}$

U P P X = P P

${\bf UPPX} = {\bf PP}$

Tayfun Pay

¿Qué tan difícil es saber si una función en #PP es siempre pareja? Espero que sea indecidible.

Peter Shor

@ PeterShor: Eso es ciertamente indecidible. Uno puede tomar una máquina que acepta si y solo si el testigo de conteo es todo 1s y la misma longitud que la entrada y M se detiene exactamente en pasos [de esa longitud].

Respuestas:

Trato de dar mi intuición por qué creo que es poco probable que esto se mantenga. Tome su problema favorito en y conviértalo en un problema en , por ejemplo, nuestra función puede ser el número de ciclos hamiltonianos en un gráfico de entrada 3-regular que contiene un cierto borde fijo. A partir de la discusión de paridad sabemos que es siempre par, por lo que puede definir y no veo ninguna razón por la cual estaría en . $PPA$ $\sharp P$ $f$ $f$ $F:=f/2$ $F$ $\sharp P$

domotorp
fuente

Bueno. Ahora estoy confundido. ¿No tiene

tres ciclos hamiltonianos?

K_{4}

$K_4$

Peter Shor

De acuerdo ... lo he comprobado. El teorema es que cada borde aparece en un número par de ciclos hamiltonianos (no dirigidos) en un gráfico de 3 regulares, no es que haya un número par de ciclos hamiltonianos en total. Entonces, el problema de conteo correcto es: dado un gráfico de tres regulares y un borde

, sea

el número de ciclos hamiltonianos en

que pasan por

. ¿

en #P?

e

$e$

f

$f$

G

$G$

e

$e$

F / 2

$F/2$

Peter Shor

De hecho, es curioso que nadie se haya dado cuenta antes ... Lo he agregado.

domotorp

Aunque generalmente estoy de acuerdo con su intuición, en este caso, creo que

realidad puede estar en #P: Sea e = (v_1, v_2) la ventaja en G. Sea u, w los vecinos de v_1 que no están ' t v_2. La siguiente máquina NP tiene rutas de aceptación de f / 2: adivina un ciclo de Hamilton que incluye el par de aristas (u, v_1) y (v_1, v_2). (El punto es que la prueba de paridad uniforme crea una biyección entre dichos ciclos de Ham. Y aquellos que incluyen (w, v_1) y (v_1, v_2).) Entonces, para que la intuición funcione, necesita algo en PPA que se transmita, por ejemplo, un argumento de conteo, o que evita una biyección fácil ...

f / 2

$f/2$

Joshua Grochow

El hecho no es cierto. Por ejemplo, es fácil comprobar que falla para todos los gráficos 3-regulares conectados en 8 vértices (consulte en.wikipedia.org/wiki/Table_of_simple_cubic_graphs#8_nodes para obtener una lista), excepto el cubo (que es transitivo por los bordes) .

Emil Jeřábek apoya a Monica