Preguntas etiquetadas con complexity-theory

10
Si , entonces es ?

Si , entonces es ? Estoy haciendo esta pregunta porque, para otras clases no deterministas, parece que siempre establece que son iguales a sus contrapartes deterministas.P=NPP=NP\mathbf{P} = \mathbf{NP}L=NLL=NL\mathbf{L} = \mathbf{NL}P=NPP=NP\mathbf{P} =

9
Dureza y direcciones de reducciones

Digamos que sabemos que el problema A es difícil, luego reducimos A al problema desconocido B para probar que B también es difícil. Como ejemplo: sabemos que 3 colores es difícil. Luego reducimos 3 colores a 4 colores. Al combinar uno de los colores en 3 colores, tiene 4 colores, ergo 4 colores es...

9
Encuentra st es -duro para cualquier

Deje que LϵLϵL_\epsilon sea ​​el lenguaje de todas las fórmulas 222 -CNF φφ\varphi , de modo que pueda satisfacerse al menos ( 12+ ϵ )(12+ϵ)(\frac{1}{2}+\epsilon) de las cláusulas de φφ\varphi . Necesito demostrar que existe ϵ′ϵ′\epsilon' st LϵLϵL_\epsilon es N PNP\mathsf{NP} -hard para cualquier...

9
Expresividad de las expresiones regulares modernas.

Recientemente hablé con un amigo sobre un sitio web que propuso desafíos de expresiones regulares, principalmente haciendo coincidir un grupo de palabras con una propiedad especial. Estaba buscando una expresión regular que coincida con cadenas como ||||||||donde el número |es primo. Inmediatamente...