Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Preliminaries Read chapter Read first chapter

2013 | OriginalPaper | Chapter

26. Fixed Parameter Analogues of PSpace and k-Move Games

Authors : Rodney G. Downey, Michael R. Fellows

Published in: Fundamentals of Parameterized Complexity

Publisher: Springer London

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We define parameterized complexity classes that allow us to investigate the complexity of k-move games. We establish a number of concrete hardness and completeness results for games such as the k-move versions of Geography and Chess. We relate these classes to bounded space computations.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Beyond W[t]-Hardness
next chapter Provable Intractability: The Class XP
Footnotes
1
Some of them, such as the WK-hierarchy will be met in Chap. 30 and the M-hierarchy found in Chap. 29 are quite new and relate to lower bounds and strong complexity hypotheses.
 
2
Flum and Grohe argue that this makes the A-hierarchy a natural analogue of the polynomial time hierarchy. The other possible analogue according to our results would be the AW[t] hierarchy. Space considerations preclude us for a discussion, and we refer the reader to [312].
 
Literature
2.
K. Abrahamson, R. Downey, M. Fellows, Fixed-parameter intractability II, in Proceedings of 10th Annual Symposium on Theoretical Aspects on Computer Science, STACS 93, Würzburg, Germany, February 25–27, 1993, ed. by P. Enjalbert, A. Finkel, K. Wagner. LNCS, vol. 665 (Springer, Berlin, 1993), pp. 374–385
3.
K. Abrahamson, R. Downey, M. Fellows, Fixed-parameter tractability and completeness. IV. On completeness for W[P] and PSPACE analogues. Ann. Pure Appl. Log. 73(3), 235–276 (1995) MathSciNetCrossRefMATH
67.
H. Björklund, S. Sandberg, S. Vorobyov, On fixed-parameter complexity of infinite games, in The Nordic Workshop on Programming Theory (NWPT’03), Åbo Akademi University, Turku, Finland, October 29–31, 2003, ed. by K. Sere, M. Waldén, A. Karlsson (Åbo Akademi, Department of Computer Science, Turku, 2003), pp. 62–64
122.
143.
J. Chen, X. Huang, I. Kanj, G. Xia, On the computational hardness based on linear FPT-reductions. J. Comb. Optim. 11(2), 231–247 (2006) MathSciNetCrossRefMATH
153.
Y. Chen, J. Flum, M. Grohe, Bounded nondeterminism and alternation in parameterized complexity theory, in Proceedings of the 18th Annual IEEE Conference on Computational Complexity, CCC 2003, Aarhus, Denmark, July 7–10, 2003 (IEEE Comput. Soc., Los Alamitos, 2003), pp. 13–29 CrossRef
243.
247.
R. Downey, M. Fellows, Parameterized Complexity. Monographs in Computer Science (Springer, Berlin, 1999) CrossRef
256.
R. Downey, M. Fellows, K. Regan, Parameterized circuit complexity and the W hierarchy. Theor. Comput. Sci. 191(1–2), 97–115 (1998) MathSciNetCrossRefMATH
258.
R. Downey, M. Fellows, U. Taylor, The parameterized complexity of relational database queries and an improved characterization of W[1], in Combinatorics, Complexity & Logic, Proceedings of DMTCS ’96, Singapore, ed. by D. Bridges, C. Calude, J. Gibbons, S. Reeves, I. Witten (Springer, Berlin, 1996), pp. 194–213
280.
S. Even, R. Tarjan, A combinatorial problem which is complete for polynomial space. J. ACM 23, 710–719 (1976) MathSciNetMATH
309.
312.
J. Flum, M. Grohe, Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series (Springer, Berlin, 2006)
313.
J. Flum, M. Grohe, M. Weyer, Bounded fixed-parameter tractability and log2 n nondeterministic bits. J. Comput. Syst. Sci. 72(1), 34–71 (2006) MathSciNetCrossRefMATH
337.
M. Garey, D. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979) MATH
602.
608.
A. Scott, U. Stege, Parameterized chess, in Parameterized and Exact Computation, Proceedings of Third International Workshop, IWPEC ’08, Victoria, Canada, May, 2008, ed. by M. Grohe, R. Niedermeier. LNCS, vol. 5018 (Springer, Berlin, 2008), pp. 172–189 CrossRef
609.
630.
Metadata
Title
Fixed Parameter Analogues of PSpace and k-Move Games
Authors
Rodney G. Downey
Michael R. Fellows
Copyright Year
2013
Publisher
Springer London
Book
Fundamentals of Parameterized Complexity

Print ISBN: 978-1-4471-5558-4

Electronic ISBN: 978-1-4471-5559-1

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-1-4471-5559-1_26

Premium Partner

    Image Credits