Was ist die kleinste Klasse von Reduzierungen, bei denen ein

Es ist üblich, die Vollständigkeit in Bezug auf logarithmische Mehrfachverringerungen zu definieren . $P$

Ich suche nach einer Komplexitätsklasse so dass es vollständige Probleme bei vielen Reduktionen gibt. $C \subseteq \mathsf{L}$ $\mathsf{P}$ $C$

Was ist die kleinste bekannte Mehrfachreduktionsklasse so dass HornSAT für unter -Reduktionen vollständig ist ? $C$ $\mathsf{P}$ $C$

Die Frage wurde ursprünglich auf CS ohne Antwort veröffentlicht.

cc.complexity-theory complexity-classes Mohammad Al-Turkistany
quelle

Vielleicht meinen Sie alle nicht trivialen Probleme: Die leere Sprache und die Sprache, deren Ergänzung leer ist, können nicht vollständig sein.

Sasho Nikolov

@SashoNikolov Klar, ich interessiere mich nicht für triviale Sprachen!

Mohammad Al-Turkistany

Ich verstehe die Frage nicht. Wenn C = P ist, sind alle Probleme in P außer den trivialen für P unter C-Reduktionen vollständig, und dies ist der Fall, unabhängig davon, was C ist.

Kaveh

@Kaveh Was ist die kleinste solche Klasse

? Ist beispielsweise HornSAT für

unter

-Reduktionen vollständig ?

C

$C$

P

$P$

N C^{1}

$NC^1$

Mohammad Al-Turkistany

Ich teile Kavehs Verwirrung über den ersten Absatz. In Bezug auf die blaue Frage ist eine vernünftige Codierung von Horn-SAT unter DLOGTIME-Reduzierungen P-vollständig.

Emil Jeřábek

Antworten:

Es ist leicht zu zeigen, dass das Schaltungswertproblem für unter -Reduktionen vollständig ist (siehe András 'Kommentar unten). $\mathsf{P}$ $\mathsf{AC^0}$

Für ein einfacheres Beispiel betrachten

A = {⟨ M, x, y ⟩ ∣ M accepts x in | y | steps}

$A = \{\langle M,x,y\rangle \mid \text{$M$ accepts $x$ in $|y|$ steps} \}$

Wenn eine Reduktionsklasse konstante Funktionen, Paarungen von Zeichenfolgen und Funktionen enthält, bei denen die Größe ihrer Ausgabe ein beliebiges Polynom begrenzen kann; dann ist für wrt vollständig . $C$ $A$ $\mathsf{P}$ $C$

Kaveh
quelle

Zur P-Vollständigkeit von CVP unter FO-Reduktionen siehe Übung 3.28 in Immermans beschreibender Komplexität .

András Salamon