Zapiski Nauchnykh Seminarov LOMI
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






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


Zapiski Nauchnykh Seminarov LOMI, 1991, Volume 192, Pages 69–73 (Mi znsl4947)  

Computational complexity of winning strategies in two player polynomial games

J. P. Jones
Abstract: Two player games of the following type are considered. A game is defined by a polynomial $P$, with integer coefficients. The number of variables in the polynomial is the length of the game. The two players alternately choose nonnegative integers $X_1,X_2,\dots,X_l$. The player having the last move wishes to make the polynomial $P(X_1,X_2,\dots,X_l)=0$. The other player wishes to make $P(X_1,X_2,\dots,X_l)\ne0$.
An old theorem of von Neumann and Zermelo states that any finite, positional, win-lose game with perfect information is determined. That is, there exists a winning strategy for one player or the other. In [4] the author proved that for $l=6$ (games of length 6) there need be no recursive (computable) winning strategy for eigher player. In the present paper, it is proved that for $l=4$, there need be no polynomial time computable winning strategy for either player.
A theorem about $NP$ completeness of problems in two player polynomial games is also given. The problem of deciding whether player I has a winning strategy in games of length $l=2$ is $NP$-complete. A proof is sketched.
English version:
Journal of Mathematical Sciences, 1994, Volume 70, Issue 4, Pages 1887–1889
DOI: https://doi.org/10.1007/BF02112429
Bibliographic databases:
Document Type: Article
UDC: 518.5
Language: Russian
Citation: J. P. Jones, “Computational complexity of winning strategies in two player polynomial games”, Computational complexity theory. Part 5, Zap. Nauchn. Sem. LOMI, 192, Nauka, Leningrad, 1991, 69–73; J. Math. Sci., 70:4 (1994), 1887–1889
Citation in format AMSBIB
\Bibitem{Jon91}
\by J.~P.~Jones
\paper Computational complexity of winning strategies in two player polynomial games
\inbook Computational complexity theory. Part~5
\serial Zap. Nauchn. Sem. LOMI
\yr 1991
\vol 192
\pages 69--73
\publ Nauka
\publaddr Leningrad
\mathnet{http://mi.mathnet.ru/znsl4947}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1118834}
\zmath{https://zbmath.org/?q=an:0835.90152}
\transl
\jour J. Math. Sci.
\yr 1994
\vol 70
\issue 4
\pages 1887--1889
\crossref{https://doi.org/10.1007/BF02112429}
Linking options:
  • https://www.mathnet.ru/eng/znsl4947
  • https://www.mathnet.ru/eng/znsl/v192/p69
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Statistics & downloads:
    Abstract page:130
    Full-text PDF :37
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024