MODULE CLASSES AND LOGARITHMIC ADVICE

被引：0

作者：

RAMACHANDRAN, J ^{[1
]}

机构：

[1] OHIO STATE UNIV,COLUMBUS,OH 43210

来源：

INFORMATION PROCESSING LETTERS | 1995年 / 55卷 / 05期

关键词：

COMPUTATIONAL COMPLEXITY; COUNTING CLASSES; ADVICE;

D O I：

10.1016/0020-0190(95)00109-P

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We show that paddable languages in MOD(k)P/log (where k is prime) that are also self-reducible are in MOD(k)P, without advice. This is an extension of similar results for self-reducible paddable sets in P/log by Balcazar and Schoning (1992).

引用

页码：241 / 245

页数：5

共 11 条

[1]

BALCAZAR J, 1992, THEORET COMPUT SCI, V99

[2]

BALCAZAR JL, 1990, STRUCTURAL COMPLEXIT, V2

[3]

BALCAZAR JL, 1988, STRUCTURAL COMPLEXIT, V1

[4] RELATIVIZED COUNTING CLASSES - RELATIONS AMONG THRESHOLDS, PARITY, AND MODS [J].

BEIGEL, R .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1991, 42 (01) :76-96

[5] COUNTING CLASSES - THRESHOLDS, PARITY, MODS, AND FEWNESS [J].

BEIGEL, R ;

GILL, J .

THEORETICAL COMPUTER SCIENCE, 1992, 103 (01) :3-23

[6] ON THE POWER OF PARITY POLYNOMIAL-TIME [J].

CAI, JY ;

HEMACHANDRA, LA .

MATHEMATICAL SYSTEMS THEORY, 1990, 23 (02) :95-106

[7] ON THE CONSTRUCTION OF PARALLEL COMPUTERS FROM VARIOUS BASES OF BOOLEAN FUNCTIONS [J].

GOLDSCHLAGER, LM ;

PARBERRY, I .

THEORETICAL COMPUTER SCIENCE, 1986, 43 (01) :43-58

[8]

KARP R, 1980, 12TH P ACM S THEOR C, P302

[9]

PAPADIMITRIOU CH, 1982, LECT NOTES COMPUT SC, V145, P269

[10] PP IS AS HARD AS THE POLYNOMIAL-TIME HIERARCHY [J].

TODA, S .

SIAM JOURNAL ON COMPUTING, 1991, 20 (05) :865-877

← 1 2 →