RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Journal history

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Fundam. Prikl. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Fundam. Prikl. Mat., 2001, Volume 7, Issue 2, Pages 597–614 (Mi fpm561)  

Mathematical Enlightenment

The complexity of algorithms of constructions by compass and straightedge

M. V. Alekhnovich, A. Ya. Belov

House of scientific and technical work of youth

Abstract: The article deals with the following problem. Assume that there are two points $A$ and $B$ on the plane, and a natural number $n$ is given. Our aim is to find the third point $C$ on the line containing $A$ and $B$ so that the length $AC$ is $n$ times larger than the length $AB$ using only a compass and a straightedge. During every step we can either construct a straight line containing two constructed points, or a circle with a constructed point as a center and with a radius equal to the distance between two constructed points. Intersections of constructed lines and circles form new constructed points. Denote the minimal number of steps necessary to solve this problem using only the compass as $C(n)$, and the minimal number of steps necessary to solve this problem using both the compass and the straightedge as $CS(n)$. We want to estimate the asymptotic behavior of the functions $C(n)$ and $CS(n)$. Our main result is the following: there exist constants $c_1, c_2>0$ such that a) $c_1\ln n\leC(n)\le c_2 \ln n$, b) $c_1\ln\ln n\leCS(n)\le\frac{c_2\ln n}{\ln\ln n}$. The most interesting result is obtained in connection with the lower bound of $CS(n)$, where purely algebraic notions, such as the height of a number etc., arise quite unexpectedly.

Full text: PDF file (897 kB)

Bibliographic databases:
UDC: 510.52+514.112
Received: 01.12.1996

Citation: M. V. Alekhnovich, A. Ya. Belov, “The complexity of algorithms of constructions by compass and straightedge”, Fundam. Prikl. Mat., 7:2 (2001), 597–614

Citation in format AMSBIB
\Bibitem{AleBel01}
\by M.~V.~Alekhnovich, A.~Ya.~Belov
\paper The complexity of algorithms of constructions by compass and straightedge
\jour Fundam. Prikl. Mat.
\yr 2001
\vol 7
\issue 2
\pages 597--614
\mathnet{http://mi.mathnet.ru/fpm561}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1866477}
\zmath{https://zbmath.org/?q=an:1017.51018}


Linking options:
  • http://mi.mathnet.ru/eng/fpm561
  • http://mi.mathnet.ru/eng/fpm/v7/i2/p597

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Фундаментальная и прикладная математика
    Number of views:
    This page:519
    Full text:134
    First page:1

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019