UP的相对完全性

The Relativized Completeness of UP

[He 88]在第三部分“UP有图灵完全语言吗”?的标题下构造了一个递归Oracle A,并且证明UP^A 无图灵完全语言。本文构造了一个NP Oracle B 并且证明UP^B 有多项式完全语言(从而也就有图灵完全语言)。

In section 3 of[He 88],under the title“Does UP have Turing Complete Languages?”the author constructs a recursive Oracle A such that UP^A has no Turing complete sets.In this paperWe construct an NP Oracle B such that UP^B does have Turing complete sets.