A SIMPLE PARALLEL ALGORITHM FOR FINDING A SATISFYING TRUTH ASSIGNMENT TO A 2-CNF FORMULA

被引：13

作者：

COOK, SA

LUBY, M

机构：

[1] Univ of Toronto, Toronto, Ont, Can, Univ of Toronto, Toronto, Ont, Can

来源：

INFORMATION PROCESSING LETTERS | 1988年 / 27卷 / 03期

关键词：

COMPUTER SYSTEMS; DIGITAL - Parallel Processing;

D O I：

10.1016/0020-0190(88)90069-5

中图分类号：

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

学科分类号：

0812 ;

摘要：

We show that the problem of finding a truth assignment which satisfies a 2-CNF formula can be solved in O(log n) time on a concurrent-read concurrent-write parallel random access machine (CRCW PRAM) with O(n**4) processors, where n is the number of variables in the formula.

引用

页码：141 / 145

页数：5

共 8 条

[1]

[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047

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

BORODIN, A .

SIAM JOURNAL ON COMPUTING, 1977, 6 (04) :733-744

[3] A TAXONOMY OF PROBLEMS WITH FAST PARALLEL ALGORITHMS [J].

COOK, SA .

INFORMATION AND CONTROL, 1985, 64 (1-3) :2-22

[4] A COMPUTING PROCEDURE FOR QUANTIFICATION THEORY [J].

DAVIS, M ;

PUTNAM, H .

JOURNAL OF THE ACM, 1960, 7 (03) :201-215

[5]

EVEN S, 1976, SIAM J COMPTNG, V5, P691

[6] PARALLEL ALGORITHMS IN GRAPH-THEORY - PLANARITY TESTING [J].

JAJA, J ;

SIMON, J .

SIAM JOURNAL ON COMPUTING, 1982, 11 (02) :314-328

[7] NEW PROBLEMS COMPLETE FOR NONDETERMINISTIC LOG SPACE [J].

JONES, ND ;

LIEN, YE ;

LAASER, WT .

MATHEMATICAL SYSTEMS THEORY, 1976, 10 (01) :1-17

[8]

KARP RM, 1984, 16TH P ANN ACM S THE, P266

← 1 →