Объединение 2 проблемы в NP в один

Question

Скажем, у меня есть детерминированная машина Turing, которая решает проблему решения S, с доступом в Oracle к проблемам B, C, которые находятся в $ np $ . Может быть решен с доступом Oracle только для ONE проблема в $ np $ ?

То есть, Can B и C как-то объединяются в одну проблему в $ np $ (Таким образом, показывая S - $ P ^ {np} $ )?

Answer 1

Есть как минимум два способа сделать это.Во-первых, предстоит принять расщепленную сумму $ B $ и $ C $ , который можно сделать вМногие способы, например $$ \ {0x: x \ in b \} \ cup \ {1y: y \ in c \}. $$ Во-вторых - использовать NP-полный язык $ l $ как Oracle.Поскольку любые проблемы в NP сводится к $ l $ в многочленом времени, вы можете имитировать $ B $ -Oracle, используя $ l $ -orcle.