UP的相对完全性

The Relativized Completeness of UP

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

Abstract: In section 3 ofHe 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.