Gibt es vollständige Probleme P und NP unter anderen Arten von Ermäßigungen?

Question

Ich weiß, dass die Komplexität der Klasse $\mathsf{P}$ hat die vollständige Probleme w.r.t.$\mathsf{NC}$ und $\mathsf{L}$ senken.

Sind diese beiden Klassen der einzige mögliche Klassen von Kürzungen, unter denen $\mathsf{P}$ hat die vollständige Probleme?

Auch, welche Klassen der Reduktion kann verwendet werden für $\mathsf{NP}$ neben polynomial-Zeit-Reduktionen?

Answer 1

Ihre Fragen enthalten einige falsche oder unklare Phrasen. Weder "Komplexitätsklasse X hat y Reduktion" noch "Wir können Y -Reduktion für Komplexitätsklassen X verwenden" ist sinnvoll. Darüber hinaus gibt es mindestens zwei Definitionen, die unter dem Namen „Polynom-Zeit-Reduktionen“ bekannt sind, die beide zur Untersuchung der NP-Vervollständigung verwendet werden: Polynomzeit viele Reduktionen und Polynomzeit-Turing-Reduktionen. In dieser Antwort werde ich jedoch den Unterschied zwischen vielen Reduzierungen und Reduzierungen ignorieren, und ich werde mich nur auf die Ressourcenbeschränkungen von Reduktionen konzentrieren, da die Antwort sonst zu lang und unkonzentriert wird.

Jetzt werde ich wiederholen, was Sie fragen möchten, und sie beantworten.

Gibt es Definitionen von Reduktionen in Bezug auf welche NP-Vervollständigung definiert werden kann, abgesehen von Polynom-Zeit-Reduktionen? Gibt es Definitionen von Reduktionen in Bezug auf welche P-Completness definiert werden kann, abgesehen von NC-Reduktionen und Log-Raum-Reduktionen?

Wie Artem und Raphael sagten, können Sie definieren, was Sie möchten.

Gibt es Definitionen von Reduktionen, die tatsächlich zur Untersuchung der NP-Vervollständigung in der Literatur verwendet werden, abgesehen von Polynom-Zeit-Reduktionen? Gibt es Definitionen von Reduktionen, die tatsächlich verwendet werden, um die P-Completness in der Literatur zu untersuchen, außer NC-Reduktionen und Log-Raum-Reduktionen?

Ja. Zum Beispiel verwendet Papadimitriou in seinem Lehrbuch [PAP94], einschließlich der Definition der NP-Vervollständigung. (Hinweis: In [PAP94] bedeutet der Begriff „L-Reduktion“ etwas, das sich völlig von der Log-Raum-Reduktion unterscheidet.) Wie bei P-Completness, NC^k Reduzierungen werden in [GHMRSS00] erwähnt. Dies ist ein Sonderfall von NC-Reduzierungen und allgemeiner als Log-Raum-Reduzierungen für k≥2.

Aber sind sie wirklich unterschiedliche Vorstellungen oder nur unterschiedliche Definitionen für denselben Begriff?

Derzeit weiß niemand. Beispielsweise sind die Log-Raum-Reduzierbarkeit und die Polynom-Zeit-Reduzierbarkeit nur dann gleichwertig, wenn L = p.

GHMRSS00] Raymond Greenlaw, H. James Hoover, Satoru Miyano, Walter L. Ruzzo, Shuji Shiraishi und Takayoshi Shoudai. Das Parallelberechnungsprojekt: Bände I - III, 2000. http://www.cs.armstrong.edu/greenlaw/research/parallel/

PAP94] Christos H. Papadimitriou. Rechenkomplexität. Addison-Wesley, 1994.

Answer 2

Beachten Sie, dass bei der Komplexitätsklasse $ C $ ein vollständiges Problem im Rahmen einer Klasse von Reduktionen $ A $ hat, das gleiche Problem für $ C $ unter und Klasse von Reduktionen mit $ A $ abgeschlossen sein wird.

Typischerweise vollständige Beweise für die Vollständigkeit haben eine viel schwächere Klasse von Reduktionen als normalerweise angegeben (z. B. unter $ mathsf {ac^0} $ Reduktion). Jede Klasse von Reduktionen, die $ mathsf {ac^0} $ enthalten, würde ausreichen und es gibt unzählige viele solcher Klassen.

Möglicherweise möchten Sie auch das folgende Papier überprüfen:

• Agrawal, M, Allender, E., Impagliazzo, R., Pitassi, T. und Rudich, S., "Reduzierung der Komplexität der Reduktion", Journal of Computational Complexity, 10, S. 117-138, 2001. Vorläufige Version in Proceedings of ACM STOC, 2001.

Answer 3

Als Artem Notizen in seinem Kommentar, die Frage ist vielmehr, unmeaning, wie Sie definieren können, was Sie wollen.Lassen Sie mich veranschaulichen, wo die Dinge beginnen, sich zu "irgendwie albern".

Einige notation:Für zwei Probleme, die $P,Q$, Schreibe $P \leq_F Q$ für einige Klassen von Funktionen $F$ wenn $f \in F$, so dass $P(x) = F(f(x))$ für alle ein $x$ (der $P$), wenn $P$ kann $F$-reduziert auf $Q$.Schreiben Sie $XC_F$ für die Klasse der $X$-vollständige Probleme mit Bezug auf $F$, das ist

$\qquad \displaystyle XC_F = \{P \in X \mid \forall Q \in X.\ Q \leq_F P \}$.

Bezeichnen ferner mit $T_X$ die Menge der (asymptotisch optimal), runtime-Funktionen von algorithmen, die Funktionen berechnen, die in einem set $X$.

Betrachten wir nun eine beliebige (Komplexität) die Klasse der Probleme, die $X$1.Wenn wir beschränken Reduzierung space $F$ in Bezug auf die Zeit Komplexität -- hier ist alles möglich-es gibt grob zwei Fälle:

• $T_F \supseteq \Omega(T_X)$2 -- ERMÄSSIGUNGEN sind nicht schneller als problem-Löser.

  In diesem Fall, $XC_F = X$ - das ist eindeutig nicht sehr interessant für die Komplexitätstheorie.Wenn man bedenkt, wie $F$ kann nützlich sein, in der Praxis, vor allem, wenn $T_F \subseteq heta(X)$;Sie reduzieren können, alle Probleme, die in $X$, um eine Handvoll von Problemen, die Sie lösen kann, sehr gut.Lineare Programmierung und SAT sind typische Beispiele, weil der hoch optimierten LP - resp.SAT-Solver.

• $T_F \subseteq o(X)$ -- Kürzungen sind schneller als Problemlöser

  Hier interessante Dinge können passieren, dass ist $XC_F eilmenge X$ oder $XC_F eq XC_{F'}$ für verschiedene Reduzierung Räume.Ob diese Tatsachen haben interessante Auswirkungen, hängt von der konkreten Wahl von $X$ und $F$.Beachten Sie, dass $XC_F = \emptyset$ passieren könnte, was an sich schon interessant genug.

  Dinge, die auf jeden Fall eher uninteressant, wenn Sie wählen Sie $F$, so "klein", dass $\leq_F$ ist spärlich, wenige Kürzungen sind möglich.Denken Sie an $X=\mathsf{NP}$ und $F$, so dass $T_F \subseteq o(n)$;Ermäßigungen müssen schrumpfen input-Größe erheblich und nicht zu viel Zeit damit verbringen, so dass $F$ ist nicht sehr mächtig.

  Beachten Sie jedoch, dass auch eine Beschränkung auf $T_F \subseteq O(1)$ Blätter sinnvolle Beziehungen;zum Beispiel, "Ist $x$ eine gerade ganze?" können reduziert werden ", Ist $x$'s erste bit 0?" in $O(1)$ Zeit und Raum.So könnte es interessant sein, zu studieren, noch so schwache Reduktionen zu finden heraus die Probleme sind in der Nähe, die anderen in Bezug auf die Reduzierung von Komplexität;Sie auf jeden Fall sehen solche Unterschiede in classic $\mathsf{NPC} = \mathsf{NP}C_P$ senken.

Technisch gesehen gibt es einen Dritten Fall, zum Beispiel $T_F = P$ und $T_X = heta(n^3)$;in diesem Fall, wenn $F$ ist ziemlich Reich -- die Kommentare auf den Fall gelten.Beachten Sie auch, dass die Frage, welcher Fall $F$ in fällt, kann interessant sein:"$\mathsf{P=NP}$?" ist im wesentlichen wissen, ob $T_F= heta(X)$ (und auch, ob $F = heta(XC_F)$).

---

1. Um eine "richtige" Komplexität der Klasse, die es braucht, um irgendeine Art von "nach unten geschlossen" w.r.t.Komplexität.
2. $\circ(X)$ für eine Funktion der Klasse $X$ und $\circ$ ein Landau-symbol ist die Natürliche Erweiterung der üblichen Landau-Symbole, D. H.$\circ(X) = \bigcup_{f \in X} \circ(f)$.