$ k $ -Coloring в BPP, подразумевает $ k $ -Coloring в ZPP

Question

Рассмотрим следующую проблему:

$ k $ -COL : Учитывая график $ G= (V, E ) $ , имеет ли у него действительный $ k $ - lecoloring?

Мне нужно доказать, что если $ k $ -oCol находится в BPP , то это тоже в <сильные> ZPP . Другими словами, показать, что если существует вероятностное алгоритм полиэтилена, которое решает, имеет ли граф действительный $ K $ - lecoling или нет с ограниченной ошибкой, то есть также вероятностный алгоритм полиэтилена, который делает это с нулевой ошибкой.

---

Моя попытка

Мне удалось доказать, что предположить, что нам разрешено вызывать Oracle, которая решает вышеуказанную проблему в полиноме (см. Ниже). Но есть ли способ показать это без предположения p ?

Пусть $ \ mathcal {a} $ Будьте полиномиальной машиной времени с доступом к Oracle для $ K $ < / span> -oCol .

Пусть $ G $ - график и пусть $ m $ Будьте bpp < / strong> ntm, который делает $ k $ -oCol Будьте в BPP . Давайте определим следующую NTM $ m '$ :

Если $ g \ in $ $ k $ Выполните $ m $ on $ g $ .

1. Если $ m (g)= 1 $ , выполнить $ \ mathcal {a} $ на $ g $ . Конечно, $ \ mathcal {a} (g)= 1 $ .
2. Если $ m (g)= 0 $ , вывод $? $ .

Если $ g \ notin $ $ k $ - - Выполните $ m $ on $ g $ .

1. Если $ m (g)= 1 $ , вывод $? $ .
2. Если $ m (g)= 0 $ , выполнить $ \ mathcal {a} $ на $ g $ . Конечно, $ \ mathcal {a} (g)= 0 $ .

Определения (для справки)

Мы определяем класс языков BUNDED-ERPALIC PROBALISTIC POLLNOMIAL-TORE (BPP) как все $ L \ SOUSTED \ \ {0,1 \} ^ * $ , для которого существует ntm $ m $ и $ C \ geq 0 $ Такое, что $ t_m=mathcal {o} (n ^ c) $ и что для всех $ x \ in \ { 0,1 \} ^ * $ :

1. $ pr [m (x) \ in \ {0,1 \}]= 1 $ ,
2. Если $ x \ in l $ , то $ pr [m (x)= 1] \ geq 3 / 4 $ ,
3. Если $ x \ notin l $ , затем $ pr [m (x)= 1] \ leq 1 / 4 $ .

Мы определяем класс языков вероятностное значение с нулевой ошибкой (ZPP) как все $ l \ subsretq \ {0,1 \} ^ * $ , для которого существует ntm $ m $ и $ C \ geq 0 $ Такое, что $ t_m=mathcal {o} (n ^ c) $ и что для всех $ x \ in \ { 0,1 \} ^ * $ :

1. $ pr [m (x) \ in \ {0,1, \ text {?} \}]= 1 $ и $ pr [m (x)=text {?}] \ leq 1/2 $ ,
2. Если $ x \ in l $ , затем $ pr [m (x)= 0]= 0 $ < / span>,
3. Если $ x \ notin l $ , затем $ PR [M (x)= 1]= 0 $ < / span>.

Answer 1

Это утверждение для моих знаний неизвестна. Если это упражнение, то, вероятно, ошибка: они означают $ RP $ вместо $ ZPP $ ?

Поскольку $ K $ -COLORING NP-CLANK, что вас просят показать:

Если $ np \ subseTQ BPP $ , затем $ NP= ZPP $ .

Во-первых, давайте рассмотрим, что известно: основные включения следующие: \ begin {align *} P \ SOUNTED ZPP \ SOUNTED RP & \ SOUNTEDQ NP \\ P \ SOUNTEDQ ZPP \ SOUNTQ CORP & \ SOUNTED CONP \\ RP & \ SOUNDED BPP \\ CORP & \ SOUNTED BPP. \ end {align *}

То есть $ p $ содержится в $ ZPP= RP \ CAP Corp $ , который содержится в $ BPP $ . Кроме того, $ RP $ содержится в $ np $ и $ CORP $ содержится в $ CONP $ . Но мы не знаем, как $ np $ и $ CONP $ относится к $ p= ZPP= BPP $ , что подразумевает, что $ Np $ и $ CONP $ содержит $ BPP $ ).

Теперь, что произойдет, если (как в вашем управлении) $ NP \ SOUNTED BPP $ ? Следует (и это общее упражнение для шоу), что $$ NP= RP. $$

(см. E.g. Здесь ). Это означает, что $$ corp= conp \\ ZPP= NP \ CAP CONP \\ $$ Таким образом, в этом случае у нас есть $ p $ , который содержит $ np $ и $ CONP $ , и те, которые содержатся в $ BPP $ (который также равен полиномиальной иерархии $ ph $ ).

Но нет никаких оснований полагать, что это подразумевает, что $ np= conp $ , который вам нужно будет показать, что ваш $ np $ - queplete Язык, $ K $ - в $ ZPP= NP \ CAP CONP $ . В частности, мы можем представить, что $ BPP $ равен второму уровню полиномиальной иерархии (вам не нужно знать с этим, но это просто некоторые Уровень, который содержит как $ np $ и $ conp $ ). Это будет подразумевать, что $ NP $ содержится в $ BPP $ , но это не значит, что < SPAN CLASS= «Математический контейнер»> $ NP $ и $ conp $ равен.

tl; dr Заявление, которое вы пытаетесь показать, кажется, неизвестен.