论文部分内容阅读
定义与研究两族函数数Ｌ．Ｖ和ＦＬ。定义这些类的方法是限制Ｌ．Ｖ的验证复杂性和ＦＬ的求值复杂性在Ｌ∈｛Ｐ，ＵＰ，ＦｅｗＰ，ＮＰ｝之内，并且限制Ｌ．Ｖ的输出值个数在Ｖ∈｛ＳＶ，ＰＶ，ＭＶ｝之内。这些类之间的包含与相等关系以及在函数复合运算下的封闭性质被完全确定。这些类不仅统一了过去已知的函数类而且定义了新的函数类，例如ＦｅｗＰ．ＰＶ．ＦｅｗＰ．ＰＶ是自然对应于ＦｅｗＰ的函数类，因为ＦｅｗＰ．ＰＶ的定义