scientific article; zbMATH DE number 1113848

MaRDI QIDQ4375622zbMATH OpenFDO

Authors Carsten Rössner, Jean-Pierre Seifert

Publication date 1 March 1998

zbMATH Keywords

2-prover 1-round interactive proof systemsapproximabilityapproximation algorithmcomputational complexitygcdlabel coverNP-completeNP-hardnumber theoretic optimizationprobabilistically checkable proofs

Mathematics Subject Classification ID

Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Number-theoretic algorithms; complexity (11Y16) Symbolic computation and algebraic computation (68W30)

Recommendations

• scientific article; zbMATH DE number 799777
• The area-time complexity of the greatest common divisor problem: A lower bound
• On the complexity of computing the greatest common divisor of several univariate polynomials
• scientific article; zbMATH DE number 1262453
• Complexity of algorithms for computing greatest common divisors of parametric univariate polynomials
• Algorithms for the approximate common divisor problem
• Algorithms for CRT-variant of approximate greatest common divisor problem
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• A lower bound for integer greatest common divisor computations
• scientific article; zbMATH DE number 1461539

Cited in

(7)

• scientific article; zbMATH DE number 4126699 (Why is no real title available?)
• Circulant graphs and GCD and LCM of subsets
• scientific article; zbMATH DE number 799777 (Why is no real title available?)
• scientific article; zbMATH DE number 1418331 (Why is no real title available?)
• On the complexity of computing the greatest common divisor of several univariate polynomials
• Approximate polynomial GCD over integers
• An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4375622)