Complement (complexitat)
En teoria de la complexitat computacional, el complement d'un problema de decisió és el problema de decisió que resulta d'invertir les respostes sí i no.[1] De manera equivalent, si es definixen els problemes de decisió com a conjunts de cadenes finitas, llavors el complement d'este conjunt sobre algun domini fix és el seu problema de complement.[2]
Característiques
[editar | editar còdic]Per eixemple, un problema important és si un número és primer. El seu complement és per a determinar si un número és compost (un número que no és primer). Ací el domini del complement és el conjunt de tots els número entero superiors a un.[3]
Existix una reducció de Turing des de cada problema fins al seu complement.[4] L'operació del complement és una involució, lo que significa que es desfà a sí mateixa, o el complement del complement és el problema original.
Pot generalisar-se este fet al complement d'una classe de complexitat, cridada classe de complement, que és el conjunt de complements de cada problema en la classe.[5] Si una classe es diu C, el seu complement es denomina convencionalment co-C. Note's que açò no és el complement de la classe de complexitat en sí mateixa com un conjunt de problemes, que contindria molts més problemes.
Es diu que una classe està tancada baix complement si el complement de qualsevol problema en la classe encara està en la classe.[6] Degut a que hi ha reduccions de Turing de cada problema al seu complement, qualsevol classe que es tanca baix les reduccions de Turing es tanca baix el complement. Qualsevol classe que es tanca baix complement és igual a la seua classe de complement. No obstant, baix la reducció de molts a un, es creu que moltes classes importants, especialment els problemes de dificultat NP, són distintes de les seues classes complementàries (encara que açò no s'ha provat).[7]
El tancament de qualsevol classe de complexitat baix les reduccions de Turing és un superconjunto d'eixa classe que es tanca baix el complement. El tancament baix complement és la classe més chicoteta d'este tipo. Si una classe es creua en el seu complement, s'obté un subconjunt (possiblement buit) que es tanca baix el complement.
Cada classe de complexitat determinista (DSPACE(f(n)), DTIME(f(n)) para totes les f(n)) es tanca baix el complement,[8] perque simplement es pot agregar un últim pas per a l'algoritme que invertix la resposta. Açò no funciona per a les classes de complexitat no determinista, perque si existixen camins de càlcul que accepten i camins que rebugen, i tots els camins invertixen la seua resposta, encara hi haurà camins que accepten i camins que rebugen — en conseqüència, la màquina accepta en abdós casos.
Alguns dels resultats de complexitat més sorprenents analisats fins a la data varen mostrar que les classes de complexitat NL i SL estan de fet tancades baix el complement, mentres que abans es creïa àmpliament que no ho estaven (vore teorema de Immerman-Szelepcsényi). Açò últim s'ha tornat menys sorprenent ara que se sap que SL és igual a L, que és una classe determinista.
Cada classe que és baixa per sí mateixa es tanca baix complement.
Referències
[editar | editar còdic]- ↑ (1993).«Encyclopedic Dictionary of Mathematics, Volume 1».MIT Press..
- ↑ (1998).«Theory of Linear and Integer Programming».John Wiley & Sons..
- ↑ (2011).«Computability and Complexity Theory».Springer..
- ↑ (2009).«Elements of Computation Theory».Springer..
- ↑ (1994).«Introduction to the Theory of Complexity».Prentice Hall.
- 133–134..
- ↑ (1999).«Introduction to Circuit Complexity: A Uniform Approach».Springer..
- ↑ (2005).«Complexity Theory: Exploring the Limits of Efficient Algorithms».Springer..
- ↑ (1999).«Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties».Springer..
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Complemento (complejidad)» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.