Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Computers, Complexity, and Intractability from the Parametric Point of View Kapitel lesen Erstes Kapitel lesen

1999 | OriginalPaper | Buchkapitel

Relationships with Classical Complexity and Limited Nondeterminism

verfasst von : R. G. Downey, M. R. Fellows

Erschienen in: Parameterized Complexity

Verlag: Springer New York

Enthalten in: Professional Book Archive

Zugang erhalten

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

search-config
loading …

In the previous chapter, we looked at some evidence that the W -hierarchy does not collapse. Here, we will begin by looking at further results that may support this hypothesis. We analyze the following question: “Does W -hierarchy collapse imply anything unreasonable in the classical complexity classes such as NP?”

Vorheriges Kapitel Another Basis for the W -Hierarchy, the Tradeoff-Theorem, and Randomized Reductions
Nächstes Kapitel The Monotone and Antimonotone Collapse Theorems: MONOTONEW[2t + 1] = W[2t] and ANTIMONOTONE W[2t + 2] = W[2t + 1]
Metadaten
Titel
Relationships with Classical Complexity and Limited Nondeterminism
verfasst von
R. G. Downey
M. R. Fellows
Copyright-Jahr
1999
Verlag
Springer New York
Buch
Parameterized Complexity

Print ISBN: 978-1-4612-6798-0

Electronic ISBN: 978-1-4612-0515-9

Copyright-Jahr: 1999

DOI
https://doi.org/10.1007/978-1-4612-0515-9_17

Neuer Inhalt

    Bildnachweise