$ k $ -Coloring à BPP, implique $ k $ -coloring dans zpp

Question

Considérez le problème suivant:

$ k $ -col : donné un graphique $ g= (v, e ) $ , a-t-il un $ K $ -Coloring?

J'ai besoin de prouver que si $ k $ -col est dans BPP , alors c'est aussi dans zpp . En d'autres termes, montrez que s'il existe un algorithme de polytime probabiliste qui décide si un graphique a un $ K $ -coloring ou non avec une erreur délimitée, alors il y a aussi un algorithme de polytime probabiliste qui le fait avec une erreur zéro.

---

Ma tentative

J'ai réussi à prouver qu'il suppose que nous sommes autorisés à appeler un oracle qui résout le problème ci-dessus en temps polynomial (voir ci-dessous). Mais existe-t-il un moyen de montrer cela sans assumer $ k $ -col $ \ en $ p ?

let $ \ mathcal {A} $ être une machine de temps polynomial avec accès à un oracle pour $ k $ < / span> -col .

let $ g $ être un graphique et laissez $ m $ être le BPP < / Strong> NTM qui fait $ K $ -col être dans BPP . Définissons la NTM suivant NTM $ M '$ :

si $ g \ in $ in $ $ k $ -col , Exécuter $ M $ ON $ G $ .

.

1. si $ m (g)= 1 $ , exécutez $ \ mathcal {A} $ $ g $ . À coup sûr, $ \ mathcal {a} (g)= 1 $ .
.
2. si $ m (g)= 0 $ , sortie $?
.

si $ g \ notin $ $ k $ -col , Exécuter $ M $ ON $ G $ .

.
1. si $ m (g)= 1 $ , sortie $
. .
2. si $ m (g)= 0 $ , exécutez $ \ mathcal {A} $ $ g $ . À coup sûr, $ \ mathcal {a} (g)= 0 $ .
.

Définitions (pour référence)

Nous définissons la classe de langues Erreur de polynôme probabiliste (BPP) comme tout $ l \ sous -éréq \ {0,1 \} ^ * $ pour lequel il existe un NTM $ M $ et $ C \ geq 0 $ telle que $ t_m=mathcal {o} (n ^ c) $ et que pour tout $ x \ in \ \ \ 0,1 \} ^ * $ :

1. $ pr [m (x) \ in \ {0,1 \ \ \ \ {0,1 \}]= 1 $ ,
2. si $ x \ in l $ , alors $ pr [m (x)= 1] \ geq 3 / 4 $ ,
3. si $ x \ notin l $ , alors $ pr [m (x)= 1] \ Leq 1 / 4 $ .

Nous définissons la classe de langues Erreur zéro-erreur polynomial-time (ZPP) comme tout $ l \ sous -éréq \ {0,1 \} ^ * $ pour lequel il existe un NTM $ M $ et $ C \ geq 0 $ telle que $ t_m=mathcal {o} (n ^ c) $ et que pour tout $ x \ in \ \ \ 0,1 \} ^ * $ :

1. $ pr [m (x) \ in \ {0,1, \ texte {?} \} \}]= 1 $ et $ pr [m (x)=text {?}] \ Leq 1/2 $ ,
2. si $ x \ in l $ , alors $ pr [m (x)= 0]= 0 $ < / span>,
3. si $ x \ notin l $ , alors $ pr [m (x)= 1]= 0 $ < / span>.

Answer 1

Cette déclaration est à ma connaissance inconnue. S'il s'agit d'un exercice, il s'agit probablement d'une erreur: ont-ils voulu dire $ rp $ au lieu de $ zpp $ $ ?

depuis $ k $ -coloring est NP-complet, ce que vous êtes invité à montrer est:

si $ n \ subteteq bpp $ $ $ , puis $ np= zpp $ $

.

.

Tout d'abord, examinons ce que l'on sait: les inclusions de base sont les suivantes: \ commence {align *} P \ Substeeq ZPP \ SubreTeQ RP & \ SubsteEQ NP \\ P \ Subreteq ZPP \ Subreteq Corp & \ Subreteq ConP \\ RP & \ SubsteEteQ BPP \\ Corp & \ Substeteq BPP. \ fin {align *}

c'est, $ p $ est contenu dans $ zpp= rp \ cap Corp $ , qui est contenu dans $ BPP $ . De plus, $ RP $ est contenu dans $ np $ et $ corp $ est contenu dans $ ConP $ . Mais nous ne savons pas comment $ np $ et $ CONP $ se rapporte à $ BPP $ (il est conjecturé que $ p= zpp= BPP $ , ce qui implique que $ Np $ $ et $ CONP $ contient $ BPP $

).

Maintenant, que se passe-t-il si (comme dans votre exercice) $ n \ sous -éréq bpp $ ? Il suit (et est un exercice commun à montrer) que $$ Np= rp. $$

(voir par exemple ici ). Cela signifie que $$ Corp= ConP \\ Zpp= np \ cap connement \\ $$ Donc, fondamentalement, dans ce cas, nous avons $ p $ , qui contient $ np $ et $ ConP $ , et ceux-ci sont tous deux contenus dans $ BPP $ (qui est également égal à la hiérarchie polynomiale $ pH $ ).

Mais il n'y a aucune raison de croire que cela implique que $ NP= CONP $ , ce que vous auriez besoin de montrer que votre $ np $ -Complète langue, $ k $ -col, est dans $ zpp= Np \ cap conique $ . En particulier, on peut imaginer que $ BPP $ est égal au deuxième niveau de la hiérarchie polynomiale (vous n'avez pas besoin de connaître cela, mais c'est juste quelques niveau contenant à la fois $ np $ $ et $ ConP $ ). Cela impliquerait que $ np $ est contenu dans $ BPP $ , mais cela ne signifie pas que < span class="math-conteneur"> $ np $ et $ CONP $ $ est égal.

tl; dr La déclaration que vous essayez de montrer semble être inconnue.