En la teoría de la complejidad computacional , SP
2es una clase de complejidad , intermedia entre el primer y segundo nivel de la jerarquía polinomial . Un idioma L está ensi existe un predicado de tiempo polinomial P tal que
- Si , entonces existe una y tal que para todo z ,,
- Si , entonces existe una z tal que para todo y ,,
donde el tamaño de y y z debe ser polinomio de x .
Relación con otras clases de complejidad
Es inmediato de la definición que SP
2Está cerrado bajo uniones, intersecciones y complementos. Comparando la definición con la de y , también se sigue inmediatamente que SP
2 está contenido en . De hecho, esta inclusión puede reforzarse a ZPP NP . [1]
Todos los idiomas en NP también pertenecen a SP
2. Porque, por definición, un lenguaje L está en NP, si y sólo si existe un verificador de tiempo polinomial V ( x , y ), tal que para cada x en L existe y para el cual V responde verdadero, y tal que para cada x no en L , V siempre responde falso. Pero tal verificador se puede transformar fácilmente en un SP
2predicado P ( x , y , z ) para el mismo idioma que ignora z y de otra manera se comporta igual que V . Del mismo modo, co-NP pertenece a SP
2. Estas inclusiones sencillas pueden reforzarse para mostrar que la clase SP
2contiene MA (por una generalización del teorema de Sipser-Lautemann ) y (más generalmente, ).
Teorema de Karp-Lipton
Una versión del teorema de Karp-Lipton establece que si cada idioma en NP tiene circuitos de tamaño polinomial, entonces la jerarquía de tiempo polinomial colapsa a SP
2. Este resultado produce un fortalecimiento del teorema de Kannan : se sabe que SP
2no está contenido en SIZE ( n k ) para ningún k fijo .
Jerarquía simétrica
Como extensión, es posible definir como operador en clases de complejidad; luego. Iteración deoperador produce una "jerarquía simétrica"; la unión de las clases así producida es igual a la jerarquía Polinomial .
Referencias
- Canetti, Ran (1996). "Más sobre BPP y la jerarquía de tiempo polinomial". Cartas de procesamiento de información . Elsevier. 57 (5): 237–241. doi : 10.1016 / 0020-0190 (96) 00016-6 .
- Russell, Alexander; Sundaram, Ravi (1998). "La alternancia simétrica captura BPP". Complejidad computacional . Birkhäuser Verlag. 7 (2): 152-162. doi : 10.1007 / s000370050007 . ISSN 1016-3328 . S2CID 15331219 .
enlaces externos
- Complejidad Zoo : S 2 P
- Clase de complejidad de la semana: S 2 P , Lance Fortnow , 28 de agosto de 2002.