SUBQUADRATIC SIMULATIONS OF BALANCED FORMULAS BY BRANCHING PROGRAMS

被引：3

作者：

CAI, JY

LIPTON, RJ

机构：

[1] Princeton Univ, Princeton, NJ

来源：

SIAM JOURNAL ON COMPUTING | 1994年 / 23卷 / 03期

关键词：

BRANCHING PROGRAMS; BOOLEAN FORMULAS; BOOLEAN CIRCUITS; GROUP THEORY;

D O I：

10.1137/S0097539790181336

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper considers Boolean formulae and their simulations by bounded width branching programs. It is shown that every balanced Boolean formula of size s can be simulated by a constant width (width 5) branching program of length s1.811.... A lower bound for the translational cost from formulae to permutation branching programs is also presented.

引用

页码：563 / 572

页数：10

共 17 条

[1]

AJTAI M, 1986, 18TH P ACM STOC, P30

[2]

ALON N, 1988, JCSS, V38, P118

[3]

BARRINGTON D, 1990, JCSS, V38, P150

[4]

BARRINGTON D, 1991, 6TH P STRUCT COMPL T, P305

[5]

BARRINGTON DA, 1987, SPRINGER LECT NOTES, V267, P163

[6]

BARRINGTON DA, 1985, TM291 MIT LAB COMP S

[7]

BENOR M, 1988, 20TH P ANN ACM S THE, P254

[8] BOUNDS FOR WIDTH 2 BRANCHING PROGRAMS [J].

BORODIN, A ;

DOLEV, D ;

FICH, FE ;

PAUL, W .

SIAM JOURNAL ON COMPUTING, 1986, 15 (02) :549-560

[9]

CAI J, 1989, 30TH P IEEE S F COMP, P568

[10]

CHANDRA AK, 1983, 15TH P ACM STOC, P94

← 1 2 →