Combinant 2 problèmes dans NP en un

Question

Dites que j'ai une machine de Turning déterministe qui résout le problème de décision S avec un accès Oracle aux deux problèmes B, C qui sont dans $ np $ . Peut être résolu avec l'accès Oracle à un seul problème un dans $ np $ ?

c'est-à-dire que B et C peut-il être associé à un problème dans un problème dans $ np $ (ainsi que montrant s est dans $ P ^ {np} $ )?

Answer 1

Il y a au moins deux façons de le faire.Le premier est de prendre une somme disjointe de $ B $ et $ C $ , qui peut être fait dansplusieurs façons, par exemple $$ \ {0x: x \ in b \} \ tasse \ {1Y: y \ in c \}. $$ La seconde consiste à utiliser une langue np-complète $ l $ comme oracle.Étant donné que tout problème dans NP réduit à $ l $ en temps polynomial, vous pouvez simuler une $ B $ -Oracle à l'aide d'un $ L $ -Oracle.