Komplexitätsklassen für andere Fälle als den „schlimmsten Fall“

Haben wir Komplexitätsklassen beispielsweise in Bezug auf die durchschnittliche Fallkomplexität? Gibt es zum Beispiel eine (benannte) Komplexitätsklasse für Probleme, deren Entscheidung die erwartete Polynomzeit benötigt?

Eine andere Frage berücksichtigt die Best-Case- Komplexität, die im Folgenden beispielhaft dargestellt wird:

Gibt es eine Klasse von (natürlichen) Problemen, deren Entscheidung mindestens exponentielle Zeit erfordert ?

Um zu klären, betrachten einige EXP -komplette Sprache . Offensichtlich erfordern nicht alle Instanzen von eine exponentielle Zeit: Es gibt Instanzen, die auch in Polynomzeit entschieden werden können. Die beste Komplexität von ist also nicht die exponentielle Zeit.L $L$$L$$L$

EDIT: Da mehrere Unklarheiten aufgetreten sind, möchte ich versuchen, dies noch genauer zu klären. Mit "Best-Case" -Komplexität meine ich eine Komplexitätsklasse, deren Komplexität durch eine Funktion niedriger begrenzt ist. Definieren Sie beispielsweise BestE als die Klasse von Sprachen, die nicht zeitlich unter einem linearen Exponential entschieden werden kann. Symbolisch sei eine beliebige Turingmaschine, und , und seien natürliche Zahlen:c n 0$M$$c$$n_0$$n$

$L \in \mathbf{BestE} \Leftrightarrow$ $\quad (\exists c)(\forall M)[(L(M) = L) \Rightarrow (\exists {n_0})(\forall n > {n_0})(\forall x \in {\{0,1\}^n})[T(M(x)) \ge {2^{c|x|}}]]$

wobei die Zeiten bezeichnet, die es dauert, bis am Eingang anhält .M $T(M(x))$$M$$x$

Ich akzeptiere, dass die Definition einer solchen Klasse von Problemen sehr seltsam ist, da wir verlangen, dass jede Turing-Maschine , unabhängig von ihrer Leistung, die Sprache nicht in einer Zeit entscheiden kann, die kleiner als ein lineares Exponential ist.$M$

Beachten Sie jedoch , dass das Gegenstück zur Polynomzeit ( BestP ) natürlich ist, da jede Turing-Maschine Zeitum zumindest seine Eingabe zu lesen.$|x|$

PS: Vielleicht müssen wir , anstatt als "für alle Turingmaschinen " zu quantifizieren , diese auf eine vorgegebene Klasse von Turingmaschinen beschränken, wie z. B. Turingmaschinen mit Polynomzeit. Auf diese Weise können wir Klassen wie definieren. ist die Klasse von Sprachen, für deren Entscheidung mindestens eine quadratische Zeit für Turing-Maschinen mit Polynomzeit erforderlich ist.B e s t ( n 2$M$$\mathbf{Best(n^2)}$

PS2: Man kann auch das Gegenstück zur Schaltungskomplexität berücksichtigen, bei dem wir die geringste Schaltungsgröße / -tiefe berücksichtigen, um eine Sprache zu bestimmen.

Obwohl ich Ihre Definitionen nicht ganz analysieren kann, sollten Sie wissen, dass viel stärkere Zeithierarchien bekannt sind, insbesondere "fast überall" Zeithierarchien.

Hier ist die formale Aussage: Für jede zeitgebundene gibt es eine Sprache L ∈ T I M E [ T ( n ) ] mit der Eigenschaft, dass jeder deterministische Algorithmus, der L korrekt erkennt , in einer Zeit asymptotisch größer als t laufen muss ( n ) an allen bis auf endlich viele Eingaben für eine ausreichend kleine Zeit t ( n ) . $T(n)$$L \in TIME[T(n)]$$L$$t(n)$$t(n)$

"Ausreichend klein" bedeutet .$t(n) \log t(n) \leq o(T(n))$

Angenommen , wir wählten für ein Beispiel, und erhält eine harte Sprache L . Dann muss jeder Algorithmus, der L korrekt erkennt , an allen Eingaben nach einer bestimmten Länge mindestens 2 n / n 2 Zeit benötigen. Dies scheint das zu sein, wonach Sie in Ihrer Klasse BestE suchen.$T(n)=2^n$$L$$L$$2^n/n^2$

Referenz:

John G. Geske, Joel I. Seiferas, Dung T. Huynh: Eine Anmerkung zu fast überall komplexen Mengen und zur Trennung deterministischer Zeit-Komplexitätsklassen Inf. Comput. 92 (1): 97 & ndash; 104 (1991)

Es gibt eine Reihe von Klassen, die versuchen, verschiedene Vorstellungen von durchschnittlicher Fallkomplexität anzugehen. Im Complexity Zoo sind einige Klassen, an denen Sie interessiert sein könnten:

Durchschn

HeurP

DistNP

(NP, P-Probenahme)

Arora / Barak deckt viele ähnliche Klassen ab (in Kapitel 18) und definiert distP, distNP und sampNP.

Die genaue Beziehung zwischen all diesen Klassen ist durch Impagliazzos Fünf Welten gekennzeichnet, nach denen zuvor in einer anderen Frage gefragt wurde .

Was die Komplexitätsfrage "Best Case" betrifft, bin ich mir nicht sicher, ob ich genau verstehe, was Sie meinen. Suchen Sie EXP ?

Wenn Sie Komplexitätsklassen meinen, die als Laufzeit im besten Fall über alle Instanzen definiert sind, ist dies kein sehr gutes Komplexitätsmaß a priori, da Sie nur die trivialen Fälle eines bestimmten Problems betrachten würden.

$TIME[T(n)]$$\mathcal{C}$$L$$\mathcal{C}$$L' \subseteq L$$L' \in \mathcal{C}$$L$$\mathcal{C}$$L$$\overline{L} = \Sigma^* \backslash L$$\mathcal{C}$$\mathbf{BestE}$$E$

(Historisch gesehen: Der Begriff der Immunität wurde 1944 von Post erstmals in der Berechenbarkeitstheorie entwickelt, lange bevor P überhaupt definiert wurde. Post betrachtete tatsächlich "einfache Mengen" - eine Menge ist einfach, wenn ihr Komplement immun ist. Für einen Berechenbarkeitstheoretiker Das Wort "immun" bedeutet normalerweise "immun gegen berechenbare Mengen". In dieser Einstellung ist Immunität gleichbedeutend mit "immun gegen ce-Mengen", da jede unendliche ce-Menge eine unendlich berechenbare Menge enthält Vorstellung von einer Reduzierung um viele, aber das konnte ich nicht schwören.)

Verschiedene Fälle sind sinnvoller, wenn es um Algorithmen geht, nicht um Probleme. Andererseits geht es bei Komplexitätsklassen um Probleme, nicht um Algorithmen. Daher ist die Komplexitätsklasse, die für jeden Algorithmus immer der schlechteste Fall ist, auf die Definition zurückzuführen.

In der Komplexität besteht Ihr Ziel darin, die Anzahl der Ressourcen zu kennen, die zur Lösung einer Instanz eines bestimmten Problems erforderlich sind. Daher wissen Sie, dass Sie für eine bestimmte Instanz und einen bestimmten Algorithmus diese Ressourcen benötigen und nicht mehr.

Bei der Algorithmusanalyse besteht Ihr Ziel darin, sicherzustellen, dass Ihr Algorithmus in jedem Fall des Problems eine Obergrenze für eine Ressource hat. Eine triviale Grenze ist die Komplexitätsklasse des Problems, da kein nützlicher Algorithmus (der unnötige Schritte ausführt) mehr Zeit benötigt. Sie können diese Grenze jedoch aufgrund der Besonderheiten des Algorithmus verbessern.

Angenommen, Sie analysieren Mergesort. Wenn die Lösung gegeben ist, können Sie sie in Polynomzeit bestätigen, daher ist SORTIEREN in NP. Durch Analyse können Sie dies jedoch auf senken.$\Theta$

Im besten Fall ist es für jedes Problem trivial, die geringste Anzahl an benötigten Ressourcen zu finden. Angenommen, die Eingabe hat die Länge O (n) und die Ausgabe die Länge O (m). Dann läuft das folgende TM M im besten Fall immer in O (n) + O (m):

M {Eingabe, Instanz, Lösung}

1. Vergleichen Sie die angegebene Instanz mit der auf dem Computer codierten Instanz.
2. Wenn sie gleich sind, geben Sie die codierte Lösung zurück.
3. Andernfalls führen Sie eine Brute-Force-Suche durch.

$O(1)$