¿Cuál es la clase más pequeña de reducciones bajo la cual hay un problema de

Es común definir la completitud de con respecto a las reducciones de espacio de registro de muchos. $P$

Estoy buscando una clase de complejidad tal manera que haya problemas completos wrt muchas- reducciones. $C \subseteq \mathsf{L}$ $\mathsf{P}$ $C$

¿Cuál es la clase reducción múltiple más pequeña conocida de tal forma que HornSAT esté completa para bajo reducciones ? $C$ $\mathsf{P}$ $C$

La pregunta se publicó originalmente en CS sin respuesta.

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

Tal vez te refieres a todos los problemas no triviales: el idioma vacío y el idioma cuyo complemento está vacío no pueden ser completos.

Sasho Nikolov

@SashoNikolov ¡Claro, no me interesan los idiomas triviales!

Mohammad Al-Turkistany

No entiendo la pregunta. Si C = P, entonces todos los problemas en P, excepto los triviales, están completos para P bajo las reducciones de C, y este es el caso independientemente de lo que C es.

Kaveh

@Kaveh ¿Cuál es la clase

más pequeña ? Por ejemplo, ¿HornSAT está completo para

bajo

Reducciones?

C

$C$

P

$P$

N C^{1}

$NC^1$

Mohammad Al-Turkistany

Comparto la confusión de Kaveh sobre el primer párrafo. Pero con respecto a la pregunta azul, una codificación razonable de Horn-SAT es P-completa bajo reducciones DLOGTIME.

Emil Jeřábek

Respuestas:

Es fácil mostrar que el problema del valor del circuito está completo para bajo las reducciones de (ver el comentario de András a continuación). $\mathsf{P}$ $\mathsf{AC^0}$

Para un ejemplo más fácil considerar

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

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

Si una clase de reducciones contiene funciones constantes, emparejamiento de cadenas y funciones donde el tamaño de su salida puede enlazar cualquier polinomio; entonces es completa para wrt . $C$ $A$ $\mathsf{P}$ $C$

Kaveh
fuente

Para la integridad de P de CVP bajo reducciones de FO, vea el ejercicio 3.28 en Complejidad descriptiva de Immerman .

András Salamon