Division par deux des fonctions dans #P

Laissez un entier fonction d'une valeur telle que est en . S'ensuit-il que est en ? Y a-t-il des raisons de croire qu'il est peu probable que cela tienne toujours? Des références que je devrais connaître? $F$ $2F$ $\#P$ $F$ $\#P$

De façon assez surprenante, cette situation est apparue (avec une constante beaucoup plus grande), pour une fonction pour laquelle est un ancien problème ouvert. $F$ $F \in? \#P$

Remarque: Je connais l'article M. Ogiwara, L. Hemachandra, Une théorie de la complexité pour les propriétés de fermeture réalisables où un problème de division par 2 connexe a été étudié (voir Thm 3.13). Leur problème est cependant différent, car ils définissent la division pour toutes les fonctions via l'opérateur au sol. Cela leur a permis de réduire rapidement les problèmes de parité.

cc.complexity-theory complexity-classes counting-complexity Igor Pak
la source

@Kaveh: Si

est une fonction

une fonction poly-temps, alors

est en

, mais

pas nécessairement (vraisemblablement ). Par exemple, il ne semble pas y avoir de raison pour que toutes les fonctions GapP non négatives soient en

, mais elles sont réductibles en

de cette façon.

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 soutient Monica

@JoshuaGrochow: Oui, c'est "Acceptez si et seulement si vous avez deviné les deux témoins 2F dans l'ordre lexicographique".

@JoshuaGrochow Si vous effectuez une division sans fonction de plancher, alors

s'effondre dans la classe de complexité suivante, que je viens de définir, via le théorème 5.9 sur le livre TCTC.

il existe un prédicat polynomial P et un polynôme q tels que, pour tout

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|$

Ensuite, il faut montrer où

appartient dans la hiérarchie de complexité. Il est à espérer que le cas

| 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

Est-il difficile de dire si une fonction dans #PP est toujours égale? Je pense que c'est indécidable.

Peter Shor

@PeterShor: C'est certainement indécidable. On peut prendre une machine qui accepte si et seulement si le témoin de comptage est tous les 1 et la même longueur que l'entrée et M s'arrête exactement [cette longueur].

Réponses:

J'essaie de donner à mon intuition pourquoi je pense que cela est peu probable. Prenez votre problème préféré dans , et convertissez-le en un problème dans , par exemple, notre fonction peut être le nombre de cycles hamiltoniens dans un graphe d'entrée 3 régulier contenant un certain bord fixe. De l'argument de la parité , nous savons que est toujours même, de sorte que vous pouvez définir et je ne vois aucune raison pour laquelle serait . $PPA$ $\sharp P$ $f$ $f$ $F:=f/2$ $F$ $\sharp P$

domotorp
la source

D'accord. Maintenant, je suis confus.

n'a- t-il pas trois cycles hamiltoniens?

K_{4}

$K_4$

Peter Shor

D'accord ... j'ai vérifié. Le théorème est que chaque arête apparaît dans un nombre pair de cycles hamiltoniens (non dirigés) dans un graphique à 3 régularités, et non pas qu'il y ait un nombre pair de cycles hamiltoniens au total. Donc le bon problème de comptage est: étant donné un graphe à trois régularités et un bord

, soit

le nombre de cycles hamiltoniens dans

qui passent par

. Est

à # P?

e

$e$

f

$f$

G

$G$

e

$e$

F / 2

$F/2$

Peter Shor

En effet, drôle que personne n'a remarqué plus tôt ... je l'ai ajouté.

domotorp

Bien que généralement je suis d'accord avec votre intuition, dans ce cas, je pense que

peut en fait être dans #P: Soit e = (v_1, v_2) le bord en G. Soit u, w les voisins de v_1 qui ne sont pas ' t v_2. La machine NP suivante a f / 2 acceptant les chemins: devinez un cycle de Hamilton qui comprend la paire d'arêtes (u, v_1) et (v_1, v_2). (Le fait est que la preuve d'une parité égale crée une bijection entre ces cycles de Ham. Et ceux qui incluent (w, v_1) et (v_1, v_2).) Donc, pour que l'intuition fonctionne, vous avez besoin de quelque chose dans PPA qui passe par exemple un argument de comptage, ou qui évite une bijection facile ...

f / 2

$f/2$

Joshua Grochow

Le fait n'est pas vrai. Par exemple, il est facile de vérifier qu'il échoue pour tous les graphes 3-réguliers connectés sur 8 sommets (voir en.wikipedia.org/wiki/Table_of_simple_cubic_graphs#8_nodes pour une liste), à l'exception du cube (qui est à bords transitifs) .

Emil Jeřábek soutient Monica le