Russian Mathematical Surveys
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Uspekhi Mat. Nauk:
Year:
Volume:
Issue:
Page:
Find




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

Russian Mathematical Surveys, 2009, Volume 64, Issue 5, Pages 787–803
DOI: https://doi.org/10.1070/RM2009v064n05ABEH004640 (Mi rm9322) 		 
This article is cited in 1 scientific paper (total in 1 paper)

Some unsolved problems in discrete mathematics and mathematical cybernetics

A. D. Korshunov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
English version PDF (477 kB) Citations (1)
References:
PDF
HTML
DOI: https://doi.org/10.1070/RM2009v064n05ABEH004640
Abstract: There are many unsolved problems in discrete mathematics and mathematical cybernetics. Writing a comprehensive survey of such problems involves great difficulties. First, such problems are rather numerous and varied. Second, they greatly differ from each other in degree of completeness of their solution. Therefore, even a comprehensive survey should not attempt to cover the whole variety of such problems; only the most important and significant problems should be reviewed. An impersonal choice of problems to include is quite hard. This paper includes 13 unsolved problems related to combinatorial mathematics and computational complexity theory. The problems selected give an indication of the author's studies for 50 years; for this reason, the choice of the problems reviewed here is, to some extent, subjective. At the same time, these problems are very difficult and quite important for discrete mathematics and mathematical cybernetics.
Bibliography: 74 items.
Keywords: graph reconstruction by subgraphs, Hamiltonian cycles, disjunctive normal forms, the snake-in-the-box problem, graph isomorphism, lower bounds, $\mathrm{NP}$-completeness, polynomial problems, Boolean functions hard to compute, cube piercing, perfect binary codes, Steiner triple systems.
Received: 28.08.2009
Russian version:
Uspekhi Matematicheskikh Nauk, 2009, Volume 64, Issue 5(389), Pages 3–20
DOI: https://doi.org/10.4213/rm9322
Bibliographic databases:
Document Type: Article
UDC: 510.5+519.1+519.7
MSC: Primary 68Qxx; Secondary 05Axx, 05Cxx, 94Bxx
Language: English
Original paper language: Russian
Citation: A. D. Korshunov, “Some unsolved problems in discrete mathematics and mathematical cybernetics”, Uspekhi Mat. Nauk, 64:5(389) (2009), 3–20; Russian Math. Surveys, 64:5 (2009), 787–803
Citation in format AMSBIB
\Bibitem{Kor09}
\by A.~D.~Korshunov
\paper Some unsolved problems in discrete mathematics and mathematical cybernetics
\jour Uspekhi Mat. Nauk
\yr 2009
\vol 64
\issue 5(389)
\pages 3--20
\mathnet{http://mi.mathnet.ru/rm9322}
\crossref{https://doi.org/10.4213/rm9322}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2588683}
\zmath{https://zbmath.org/?q=an:1185.68346}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2009RuMaS..64..787K}
\elib{https://elibrary.ru/item.asp?id=20425316}
\transl
\jour Russian Math. Surveys
\yr 2009
\vol 64
\issue 5
\pages 787--803
\crossref{https://doi.org/10.1070/RM2009v064n05ABEH004640}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000276915500001}
\elib{https://elibrary.ru/item.asp?id=15303038}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77149122379}
Linking options:
  • https://www.mathnet.ru/eng/rm9322
  • https://doi.org/10.1070/RM2009v064n05ABEH004640
  • https://www.mathnet.ru/eng/rm/v64/i5/p3
    • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Успехи математических наук Russian Mathematical Surveys
    Statistics & downloads:
    Abstract page:2754
    Russian version PDF:823
    English version PDF:38
    References:65
    First page:145
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024