Sharp P

Sharp P

Die Komplexitätsklasse #P (englische Aussprache Sharp-P oder Number-P) ist eine Klasse von so genannten Zählproblemen (im Gegensatz zu den meist betrachteten Komplexitätsklassen, die Entscheidungsprobleme behandeln). Viele #P-Probleme sind eng verwandt mit den zugehörigen NP-Problemen.

Die Klasse wurde 1979 von Leslie Valiant eingeführt.

Inhaltsverzeichnis

Definition

Ein Problem ist in der Klasse #P, wenn eine nichtdeterministische Turingmaschine existiert, die polynomiell zeitbeschränkt ist und für jede Instanz I des Problems genau so viele akzeptierende Berechnungspfade hat, wie es Lösungen zu der Instanz I gibt.

Beispiel

Ein bekanntes Entscheidungsproblem aus NP ist das Erfüllbarkeitsproblem der Aussagenlogik (SAT):

  • Existiert zu einer gegebenen aussagenlogischen Formel eine erfüllende Variablenbelegung?

Das zugehörige Zählproblem aus #P wird mit #SAT bezeichnet und lautet:

  • Wie viele erfüllende Variablenbelegungen gibt es zu einer gegebenen aussagenlogischen Formel?

Eigenschaften

Nach dem Satz von Toda reichen deterministische polynomiell zeitbeschränkte Turingmaschinen, die eine einzige Orakel-Anfrage an ein Problem aus #P stellen dürfen, um die Sprachen in PH zu entscheiden. Dies ist ein Hinweis für die enorme Schwierigkeit, #P-Probleme exakt zu lösen. Andererseits kann in polynomiellem Platz der Berechnungsbaum einer nichtdeterministischen, polynomiell zeitbeschränkten Turingmaschine vollständig durchsucht werden, so dass sich alle #P-Probleme in polynomiellen Platz berechnen lassen. Damit lässt sich #P wie folgt in Beziehung zu anderen wichtigen Komplexitätsklassen setzen:

P ⊆ NP ⊆ PH ⊆ P#P ⊆ PSPACE

Liste einiger #P-vollständiger Probleme

  • #SAT
  • Anzahl der perfekten Matchings eines bipartiten Graphen
Diese Tatsache ist besonders interessant, weil das zugehörige Entscheidungsproblem (Existenz von perfekten Matchings in bipartiten Graphen) deterministisch in polynomieller Zeit lösbar ist.
  • Permanente (einer 0-1-Matrix)
  • Anzahl der linearen Erweiterungen einer partiellen Ordnung [1]

Literatur

  • Leslie G. Valiant: The complexity of computing the permanent. Theoretical Computer Science, 8:189-201, 1979
  • Graham Brightwell, Peter Winkler: Counting linear extensions, Order, Volume 8, Issue 3, Sep 1991, Pages 225 - 242, DOI 10.1007/BF00383444, [2]

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Sharp — Sharp, a. [Compar. {Sharper}; superl. {Sharpest}.] [OE. sharp, scharp, scarp, AS. scearp; akin to OS. skarp, LG. scharp, D. scherp, G. scharf, Dan. & Sw. skarp, Icel. skarpr. Cf. {Escarp}, {Scrape}, {Scorpion}.] 1. Having a very thin edge or fine …   The Collaborative International Dictionary of English

  • Sharp — K.K Rechtsform Kabushiki kaisha ISIN JP3359600008[1] Gründung …   Deutsch Wikipedia

  • SHARP —  Pour l’article homophone, voir Sharpe. Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • sharp — [ʆɑːp ǁ ʆɑːrp] adjective a sharp increase, fall etc is very sudden and very big: • a sharp rise in interest rates • Unemployment generally brings a sharp fall in income. • The group reported a sharp decline in full year profits. sharply adverb …   Financial and business terms

  • sharp — [shärp] adj. [ME < OE scearp, akin to Ger scharf, ON skarpr < IE * (s)kerb(h) < base * (s)ker , to cut > SHEAR, HARVEST, L caro, flesh] 1. suitable for use in cutting or piercing; having a very thin edge or fine point; keen 2. having… …   English World dictionary

  • sharp — sharp, keen, acute can all mean having a fine point or edge, but it is in several of their extended senses that they are most likely to come into comparison. As applied to persons or their qualities, especially of intellect, all three can… …   New Dictionary of Synonyms

  • Sharp — may refer to: *Sharp (music), a musical notation sign (music|sharp) *Sharp (flour), a flour made from hard wheat *Sharp (set theory) *Sharp (crater), a lunar impact crater *Sharp (material property)An organization: *Sharp Corporation, a Japanese… …   Wikipedia

  • sharp — [adj1] knifelike, cutting aciculate, acuate, acuminate, acuminous, acute, apical, barbed, briery, cuspate, cuspidate, edged, fine, ground fine, honed, horned, jagged, keen, keen edged, knife edged, needlelike, needle pointed, peaked, pointed,… …   New thesaurus

  • sharp — sharp; sharp·en; sharp·en·er; sharp·er; sharp·ie; sharp·ish; sharp·ite; sharp·ly; sharp·ness; sharp·ster; un·sharp; …   English syllables

  • Sharp — Sharp, adv. 1. To a point or edge; piercingly; eagerly; sharply. M. Arnold. [1913 Webster] The head [of a spear] full sharp yground. Chaucer. [1913 Webster] You bite so sharp at reasons. Shak. [1913 Webster] 2. Precisely; exactly; as, we shall… …   The Collaborative International Dictionary of English

  • Sharp EL-8 — von 1971 Der EL 8 von Sharp ist der erste mobile elektronische Taschenrechner der Welt, der in Serie gefertigt wurde. Er wurde im Januar 1971 eingeführt. Die Elektronik ist in vier von Rockwell hergestellten LSI ICs (large scale integration)… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”