OMEGA(N LOG N) LOWER BOUNDS ON LENGTH OF BOOLEAN-FORMULAS

被引：16

作者：

FISCHER, MJ

MEYER, AR

PATERSON, MS

机构：

[1] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139

[2] UNIV WARWICK,COVENTRY CV4 7AL,W MIDLANDS,ENGLAND

来源：

关键词：

D O I：

10.1137/0211033

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：416 / 427

页数：12

共 23 条

[1]

[Anonymous], 1942, J MATH PHYS

[2] RELATING TIME AND SPACE TO SIZE AND DEPTH [J].

BORODIN, A .

[3]

Fischer M. J., 1975, 7 ANN ACM S THEOR CO, P37

[4] LOGICAL COMPLEXITY OF GEOMETRIC PROPERTIES IN PLANE [J].

HODES, L .

[5]

Hodes L., 1968, CONTRIBUTIONS MATH L, P175

[6]

Khasin L. S., 1970, Soviet Physics - Doklady, V14, P1149

[7]

KHRAPCENKO VM, 1976, PROBLEMY KIBERNETIKI, V31, P231

[8]

Khrapchenko V. M., 1972, MATH NOTES, V11, P70

[9]

KHRAPCHENKO VM, 1971, MAT ZAMETKI, V9, P35

[10]

KLEIMAN M, 1977, THEORET COMPUT SCI, V7, P325