COMPUTING FUNCTIONS WITH PARALLEL QUERIES TO NP

被引:35
作者
JENNER, B
TORAN, J
机构
[1] UNIV POLITECN CATALUNYA, DEPT LLENGUATGES & SISTEMES INFORMAT, E-08028 BARCELONA, SPAIN
[2] TECH UNIV MUNICH, FAK INFORMAT, D-80290 MUNICH, GERMANY
关键词
D O I
10.1016/0304-3975(94)00080-3
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The class Theta(2)(p) of languages polynomial-time truth-table reducible to sets in NP has a wide range of different characterizations. We consider several functional versions of Theta(2)(p) based on these characterizations. We show that in this way the three function classes FL(log)(NP),, FPlogNP, and FPparallel toNP are obtained. In contrast to the language case the function classes seem to all be different. We give evidence in support of this fact by showing that FL(log)(NP) coincides with any of the other classes then L=P, and that the equality of the classes FPlogNP and FPparallel toNP would imply that the number of nondeterministic bits needed for the computation of any problem in NP can be reduced by a polylogarithmic factor, and that the problem can be computed deterministically with a subexponential time bound of order 2(no(1/log log n)).
引用
收藏
页码:175 / 193
页数:19
相关论文
共 44 条
[11]   ENUMERATIVE COUNTING IS HARD [J].
CAI, JY ;
HEMACHANDRA, LA .
INFORMATION AND COMPUTATION, 1989, 82 (01) :34-44
[12]  
CASTRO J, 1992, LECT NOTES COMPUT SC, V577, P305
[13]   CONSTANT DEPTH REDUCIBILITY [J].
CHANDRA, AK ;
STOCKMEYER, L ;
VISHKIN, U .
SIAM JOURNAL ON COMPUTING, 1984, 13 (02) :423-439
[14]  
CHEN ZZ, UNPUB COMPLEXITY COM
[15]   CLASSES OF BOUNDED NONDETERMINISM [J].
DIAZ, J ;
TORAN, J .
MATHEMATICAL SYSTEMS THEORY, 1990, 23 (01) :21-32
[16]   THE COMPLEXITY OF PROMISE PROBLEMS WITH APPLICATIONS TO PUBLIC-KEY CRYPTOGRAPHY [J].
EVEN, S ;
SELMAN, AL ;
YACOBI, Y .
INFORMATION AND CONTROL, 1984, 61 (02) :159-173
[17]  
FELLOWS MR, 1992, 7TH P IEEE STRUCT CO, P107
[18]  
FENNER S, 1993, LECTURE NOTES COMPUT, V665, P398
[19]  
HEMACHANDRA L, 1986, TR86777 CORN U DEP C
[20]   THE LOGARITHMIC ALTERNATION HIERARCHY COLLAPSES - A-SIGMA-L/2=ANL/2 [J].
JENNER, B ;
KIRSIG, B ;
LANGE, KJ .
INFORMATION AND COMPUTATION, 1989, 80 (03) :269-288