关于NP分解的研究

摘要

Ker-Ⅰ和UweSch(o)ning给出了NP的一个分解,定义了语言类(^L)pn和(^H)pn,并且证明了对每一个自然数n,若PH≠Δpn,则(^L)pn∩(^H)pn=φ.本文对该分解做进一步的探讨,考虑是否存在A∈NP-{φ,∑*},使得A(∈)(^L)pn且A(∈)(^H)pn?为此,先给出一些术语.本文所涉及到的集合,都是∑={0,1}上的语言.