$ k $ -Coloring in BPP, implica $ K $ -Coloring in ZPP

Question

Considera il prossimo problema:

$ k $ -COL : dato un grafico $ g= (v, e ) $ , ha una $ k $ -Coloring?

Devo dimostrare che se $ k $ -COL è in BPP , allora è anche in ZPP . In altre parole, mostrare che se esiste un algoritmo di polytime probabilistico che decide se un grafico ha un grafico $ k $ -Coloring o no con errore limitato, quindi c'è anche Un algoritmo di polytime probabilistico che lo fa con l'errore zero.

---

.

il mio tentativo

Sono riuscito a dimostrarlo assumendo che ci è permesso chiamare un Oracle che risolve il problema di cui sopra in tempo polinomiale (vedi sotto). Ma c'è un modo per mostrarlo senza assumere $ k $ -COL $ \ in $ P ?

Let $ \ Mathcal {A} $ essere una macchina del tempo polinomiale con accesso a un'oracle per $ k $ <> $ k $ < / span> -COL .

Let $ G $ Sii un grafico e lascia che $ m $ essere il BPP < / Strong> NTM che rende $ k $ -COL essere in BPP . Definiamo il seguente ntm $ m '$ :

se $ G \ in $ $ k $ -Col , Esegui $ m $ su $ G $ .

.
1. se $ m (g)= 1 $ , eseguire $ \ mathcal {A} $ On $ G $ . Di sicuro, $ \ Mathcal {A} (G)= 1 $ .
2. se $ m (g)= 0 $ , output $? $ .

Se $ G \ Notino $ $ k $ -Col , Esegui $ m $ su $ G $ .

.
1. se $ m (g)= 1 $ , output $? $ .
2. se $ m (g)= 0 $ , eseguire $ \ mathcal {A} $ On $ G $ . Di sicuro, $ \ Mathcal {A} (G)= 0 $ .

Definizioni (per riferimento)

Definiamo la classe delle lingue Limitato-errore probabilistico Polynomial-time (BPP) come tutte le $ L \ SOTETEQ \ {0,1 \} ^ * $ per il quale esiste una ntm $ m $ e $ c \ geq 0 $ Tale che $ t_m=mathcal {o} (n ^ c) $ e che per tutti $ x \ in \ { 0,1 \} ^ * $ :

.
1. $ PR [m (x) \ in \ {0,1 \}]= 1 $ ,
2. se $ x \ in l $ , quindi $ PR [m (x)= 1] \ geq 3 / 4 $ ,
3. se $ x \ notin l $ , quindi $ PR [m (x)= 1] \ leq 1 / 4 $ .

Definiamo la classe delle lingue Errore zero Probabilistico Polynomial-Time (ZPP) come tutte $ L \ SOTETEQ \ {0,1 \} ^ * $ per il quale esiste una ntm $ m $ e $ c \ geq 0 $ Tale che $ t_m=mathcal {o} (n ^ c) $ e che per tutti $ x \ in \ { 0,1 \} ^ * $ :

.
1. $ PR [m (x) \ in \ {0,1, \ testo {?}}]= 1 $ e $ PR [m (x)=testo {?}] \ leq 1/2 $ ,
2. se $ x \ in l $ , quindi $ PR [m (x)= 0]= 0 $ < / SPAN>,
3. se $ x \ notin l $ , quindi $ PR [m (x)= 1]= 0 $ < / span>.

Answer 1

Questa affermazione è per le mie conoscenze sconosciute. Se questo è un esercizio, allora è probabile un errore: intendevano $ rp $ anziché $ ZPP $ ?

Dal momento che $ k $ -Coloring è NP-Complete, ciò che ti viene chiesto di mostrare è:

.

se $ NP \ SOTETEQ BPP $ , quindi $ NP= ZPP $ .

In primo luogo, esaminiamo ciò che è noto: le inclusioni di base sono le seguenti: \ begin {allinea *} P \ SOCSETEQ ZPP \ SOTETEQ RP & \ SOTETEQ NP \\ P \ SOCSETEQ ZPP \ SOTETETQ CORP & \ SOTETEQ CONP \\ RP & \ SOTETEQ BPP \\ Corp & \ SOTETEQ BPP. \ end {allinea *}

cioè, $ P $ è contenuto in $ zpp= rp \ cap corp $ , che è contenuto in $ BPP $ . Inoltre, $ RP $ è contenuto in $ np $ e $ Corp $ è contenuto in $ conp $ . Ma non sappiamo come $ NP $ e $ conp $ relativi a $ BPP $ (è congetturato che $ P= ZPP= BPP $ , che implica che $ NP $ e $ conp $ contenere $ BPP $ ).

Ora, cosa succede se (come nel tuo esercizio) $ NP \ SOCSETEQ BPP $ ? Segue (ed è un esercizio comune da mostrare) $$ Np= rp. $$

(vedi ad esempio qui ). Ciò significa che $$ Corp= CONP \\ ZPP= NP \ Cap Conp \\ $$ Così fondamentalmente in questo caso, abbiamo $ P $ , che contiene $ NP $ e $ CONP $ , e quelli sono entrambi contenuti in $ BPP $ (che equivale anche alla gerarchia polinomiale $ pH $ ).

Ma non c'è motivo di credere che ciò implica che $ np= conp $ , che è ciò che dovresti mostrare la tua $ NP $ Lingua - -Completa lingua, $ k $ -Col, è in $ ZPP= Np \ cap conp $ . In particolare, possiamo immaginare che $ BPP $ è uguale al secondo livello della gerarchia polinomiale (non è necessario avere familiarità con questo, ma è solo un po ' Livello che contiene sia $ NP $ e $ CONP $ ). Questo implicherebbe che $ NP $ è contenuto in $ BPP $ , ma non significa < Span class="Math-Container"> $ NP $ e $ CONP $ sono uguali.

TL; DR L'istruzione che stai cercando di mostrare sembra essere sconosciuta.