Skip to main content

2013 | OriginalPaper | Buchkapitel

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

verfasst von : Rodney G. Downey, Michael R. Fellows

Erschienen in: Fundamentals of Parameterized Complexity

Verlag: Springer London

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Fußnoten
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].
 
Literatur
2.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat L. Cai, J. Chen, R. Downey, M. Fellows, Advice classes of parameterized tractability. Ann. Pure Appl. Log. 84, 119–138 (1997) MathSciNetCrossRefMATH L. Cai, J. Chen, R. Downey, M. Fellows, Advice classes of parameterized tractability. Ann. Pure Appl. Log. 84, 119–138 (1997) MathSciNetCrossRefMATH
143.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat R. Downey, M. Fellows, Fixed-parameter tractability and completeness. I. Basic results. SIAM J. Comput. 24(4), 873–921 (1995) MathSciNetCrossRefMATH R. Downey, M. Fellows, Fixed-parameter tractability and completeness. I. Basic results. SIAM J. Comput. 24(4), 873–921 (1995) MathSciNetCrossRefMATH
247.
Zurück zum Zitat R. Downey, M. Fellows, Parameterized Complexity. Monographs in Computer Science (Springer, Berlin, 1999) CrossRef R. Downey, M. Fellows, Parameterized Complexity. Monographs in Computer Science (Springer, Berlin, 1999) CrossRef
256.
Zurück zum Zitat R. Downey, M. Fellows, K. Regan, Parameterized circuit complexity and the W hierarchy. Theor. Comput. Sci. 191(1–2), 97–115 (1998) MathSciNetCrossRefMATH R. Downey, M. Fellows, K. Regan, Parameterized circuit complexity and the W hierarchy. Theor. Comput. Sci. 191(1–2), 97–115 (1998) MathSciNetCrossRefMATH
258.
Zurück zum Zitat 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 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.
Zurück zum Zitat S. Even, R. Tarjan, A combinatorial problem which is complete for polynomial space. J. ACM 23, 710–719 (1976) MathSciNetMATH S. Even, R. Tarjan, A combinatorial problem which is complete for polynomial space. J. ACM 23, 710–719 (1976) MathSciNetMATH
309.
312.
Zurück zum Zitat J. Flum, M. Grohe, Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series (Springer, Berlin, 2006) J. Flum, M. Grohe, Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series (Springer, Berlin, 2006)
313.
Zurück zum Zitat 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 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.
Zurück zum Zitat M. Garey, D. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979) MATH M. Garey, D. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979) MATH
602.
608.
Zurück zum Zitat 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 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
630.
Metadaten
Titel
Fixed Parameter Analogues of PSpace and k-Move Games
verfasst von
Rodney G. Downey
Michael R. Fellows
Copyright-Jahr
2013
Verlag
Springer London
DOI
https://doi.org/10.1007/978-1-4471-5559-1_26