NONLINEAR ALGEBRA AND OPTIMIZATION ON RINGS ARE HARD

被引：4
作者：
HUNT, HB
STEARNS, RE
机构：
来源：
SIAM JOURNAL ON COMPUTING | 1987年 / 16卷 / 05期
关键词：
Computer metatheory - Optimization;
D O I：
10.1137/0216059
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Several general NP- or coNP-hardness results are presented for nonlinear algebraic and optimization problems on rings. Several additional related nonlinear problems for such rings are shown to be NP-, coNP-, or #P-hard. In particular, a variant of Hilbert's Tenth Problem is shown to be NP-complete.
引用
收藏
页码：910 / 929
页数：20
相关论文
共 22 条
[1]  
ABBOTT JC, 1969, SETS LATTICES BOOLEA
[2]  
ADLEMAN L, 1975, 16TH P ANN IEEE S F, P169
[3]  
[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047
[4]  
Birkhoff G., 1967, LATTICE THEORY
[5]  
BLONIARZ PA, 1984, J ACM, V31, P879, DOI 10.1145/1634.1639
[6]  
Davis M., 1982, COMPUTABILITY UNSOLV
[7]   COMPLEXITY OF PROBLEMS IN GAMES, GRAPHS AND ALGEBRAIC EQUATIONS [J].
FRAENKEL, AS ;
YESHA, Y .
DISCRETE APPLIED MATHEMATICS, 1979, 1 (1-2) :15-30
[8]  
Garey MR., 1979, COMPUTERS INTRACTABI
[9]  
HUNT HB, UNPUB DISTRIBUTIVE L
[10]  
HUNT HB, UNPUB NONLINEAR ALGE
123