LOWER BOUNDS FOR SOLVING LINEAR DIOPHANTINE EQUATIONS ON RANDOM-ACCESS MACHINES

被引：11

作者：

MEYER, F

DERHEIDE, A

机构：

[1] Johann Wolfgang Goethe-Univ, Frankfurt, West Ger, Johann Wolfgang Goethe-Univ, Frankfurt, West Ger

来源：

JOURNAL OF THE ACM | 1985年 / 32卷 / 04期

关键词：

COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1145/4221.4250

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The author proves lower bounds for the time complexity of deciding the solvability of Diophantine linear equations with n variables; that is, of deciding whether a given linear equation has a solution with nonnegative integer coefficients.

引用

页码：929 / 937

页数：9

共 10 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st

[2]

[Anonymous], 1979, COMPUTERS INTRACTABI

[3]

Blaschke Wilhelm, 1914, JAHRESBER DTSCH MATH, V23, P369

[4]

DOBKIN D, 1975, J COMPUT SYST SCI, V16, P417

[5]

HEIDE FMAD, 1984, J ACM, V31, P668, DOI 10.1145/828.322450

[6]

KANNAN R, 1983, 15TH P ANN ACM S THE, P193

[7] A LOWER TIME BOUND FOR THE KNAPSACK-PROBLEM ON RANDOM-ACCESS MACHINES [J].

KLEIN, P ;

AUFDERHEIDE, FM .

ACTA INFORMATICA, 1983, 19 (04) :385-395

[8]

LAUTEMANN C, UNPUB INF PROC LETT

[9]

LENSTRA HW, 1981, 8103 U AMST MATH I R

[10]

[No title captured]

← 1 →