THE COMPLEXITY OF EQUIVALENCE FOR COMMUTATIVE RINGS

被引：29

作者：

HUNT, HB

STEARNS, RE

机构：

[1] Computer Science Department, State University of New York at Albany, Albany, New York

来源：

JOURNAL OF SYMBOLIC COMPUTATION | 1990年 / 10卷 / 05期

关键词：

D O I：

10.1016/S0747-7171(08)80053-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the deterministic time complexity of the equivalence problems for formulas and for straight-line programs on commutative rings. A general theorem is presented, that yields sufficient conditions on a commutative ring, for these problems for the ring to require “essentially as much deterministic time as the set of satisfiable 3CNF formulas”. As corollaries of this theorem, we characterize the deterministic time complexity of these two equivalence problems, for all finite commutative rings and for all commutative unitary rings of zero or prime characteristic. © 1990, Academic Press Limited. All rights reserved.

引用

页码：411 / 436

页数：26

共 17 条

[1]

ABBOTT JC, 1969, SETS LATTICES BOOLEA

[2]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[3]

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

[4]

Behrens E. A., 1972, RING THEORY

[5]

Birkhoff G., 1979, LATTICE THEORY, V25

[6]

BLONIARZ PA, 1984, J ACM, V31, P879, DOI 10.1145/1634.1639

[7]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[8] NONLINEAR ALGEBRA AND OPTIMIZATION ON RINGS ARE HARD [J].

HUNT, HB ;

STEARNS, RE .

SIAM JOURNAL ON COMPUTING, 1987, 16 (05) :910-929

[9] THE COMPLEXITY OF VERY SIMPLE BOOLEAN-FORMULAS WITH APPLICATIONS [J].

HUNT, HB ;

STEARNS, RE .

SIAM JOURNAL ON COMPUTING, 1990, 19 (01) :44-70

[10]

HUNT HB, 1983, COMBINATORICS WORDS, P333

← 1 2 →