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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Preliminaries Kapitel lesen Erstes Kapitel lesen

2011 | OriginalPaper | Buchkapitel

11. Introduction to Counting Classes

verfasst von : Steven Homer, Alan L. Selman

Erschienen in: Computability and Complexity Theory

Verlag: Springer US

Einloggen

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

search-config
loading …

Abstract

Our interest in nondeterministic polynomial time-bounded Turing machines has been concerned primarily with the question of whether, given an input x, there exists at least one accepting computation. However, this is not entirely so, for the definition of PP is that the majority of computations are accepting. Now we will be interested in the following classes, which use counting explicitly in their definitions.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Probabilistic Complexity Classes
Nächstes Kapitel Interactive Proof Systems
Fußnoten
1
We can define an appropriate many-one reduction between functions in order to formalize this notion, but leave this to the reader.
 
2
∃!x is a quantifier denoting “there exists a unique x.”
 
3
Recall that
$${(a + b)}^{3} = {a}^{3} + 3{a}^{2}b + 3a{b}^{2} + {b}^{3}$$
and
$${(a + b)}^{4} = {a}^{4} + 4{a}^{3}b + 6{a}^{2}{b}^{2} + 4a{b}^{3} + {b}^{4}.$$
 
4
To see this, note that a 1 is added to the low order bits of the sum whenever g(〈x, y〉) is odd, and in either case (odd or even), everything else added to the sum is at least \({2}^{\vert x{\vert }^{k}+1 }\), so does not affect the low order bits.
 
Metadaten
Titel
Introduction to Counting Classes
verfasst von
Steven Homer
Alan L. Selman
Copyright-Jahr
2011
Verlag
Springer US
Buch
Computability and Complexity Theory

Print ISBN: 978-1-4614-0681-5

Electronic ISBN: 978-1-4614-0682-2

Copyright-Jahr: 2011

DOI
https://doi.org/10.1007/978-1-4614-0682-2_11

Premium Partner

    Bildnachweise