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

28. Another Basis for the W-Hierarchy and the Tradeoff Theorem

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 give a uniform circuit basis for the W-hierarchy. We introduce the syntactic classes G[t] and prove the Replacement and Tradeoff Theorems. These lead to evidence that the W-hierarchy is proper and give a different perspective on its naturality.

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 Provable Intractability: The Class XP
next chapter The M-Hierarchy, and XP-Optimality
Literature
84.
H. Bodlaender, R. Downey, M. Fellows, T. Wareham, The parameterized complexity of sequence alignment and consensus. Theor. Comput. Sci. 147(1–2), 31–54 (1994) MathSciNet
106.
R. Boppana, M. Sipser, The complexity of finite functions, in Handbook of Theoretical Computer Science, vol. A, ed. by J. van Leeuwen (MIT Press, Cambridge, 1990), pp. 757–804
243.
256.
R. Downey, M. Fellows, K. Regan, Parameterized circuit complexity and the W hierarchy. Theor. Comput. Sci. 191(1–2), 97–115 (1998) MathSciNetCrossRefMATH
557.
A. Paz, S. Moran, Nondeterministic polynomial optimization problems and their approximations. Theor. Comput. Sci. 15, 251–277 (1981) MathSciNetCrossRefMATH
620.
M. Sipser, A complexity theoretic approach to randomness, in Proceedings of 15th ACM Symposium on Theory of Computing (STOC ’83), Boston, Massachusetts, USA, May 25–May 27, 1983, ed. by D. Johnson, et al. (ACM, New York, 1983), pp. 330–335
Metadata
Title
Another Basis for the W-Hierarchy and the Tradeoff Theorem
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_28

Premium Partner

    Image Credits