Hispanopedia Wiki
Esta es una lista de clases de complejidad en la teoría de la complejidad computacional . Para otros temas de computación y complejidad, consulte la lista de temas de computabilidad y complejidad .
Muchas de estas clases tienen un complemento «co» que consiste en los complementos de todas las lenguas de la clase original. Por ejemplo, si una lengua L pertenece a NP, entonces el complemento de L pertenece a co-NP. (Esto no significa que el complemento de NP sea co-NP; hay lenguas que se sabe que pertenecen a ambas clases, y otras que no pertenecen a ninguna).
Los "problemas más difíciles" de una clase se refieren a problemas que pertenecen a esa clase de tal manera que cualquier otro problema de esa clase se puede reducir a él.
Referencias
- 1 2 3 Sanjeev Arora, Boaz Barak (2009), Complejidad computacional: un enfoque moderno , Cambridge University Press; 1.ª edición, ISBN 978-0-521-42426-4
- ↑ "S 2 P: Segundo nivel de la jerarquía simétrica" . Stanford University Complexity Zoo. Archivado del original el 14 de octubre de 2012. Consultado el 27 de octubre de 2011 .
Enlaces externos
- Complexity Zoo : lista de más de 500 clases de complejidad y sus propiedades.
Categorías :
- Clases de complejidad
- Listas relacionadas con las matemáticas
