On the ultimate complexity of factorials

DOI10.1016/J.TCS.2004.06.020zbMATH Open1079.11060OpenAlexW2007080245MaRDI QIDQ703565FDOQ703565

Qi Cheng

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.06.020

zbMATH Keywords

factorizationelliptic curvecomputational and structural complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Number-theoretic algorithms; complexity (11Y16)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Factoring integers with elliptic curves
• Torsion points on elliptic curves and \(q\)-coefficients of modular forms
• Torsion points on elliptic curves defined over quadratic fields
• On a problem of Oppenheim concerning Factorisatio Numerorum
• Factoring numbers in O(log n) arithmetic steps
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• Some results on computational complexity

Cited In (5)

• Algebraic Complexity Classes
• Generic hardness of inversion on ring and its relation to self-bilinear map
• Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
• Counting arithmetic formulas
• On the complexity of calculating factorials

This page was built for publication: On the ultimate complexity of factorials

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