Wikipedia

Diferencia entre revisiones de «Clase de complejidad»

Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
RobotQuistnix (discusión · contribs.)
180 567 ediciones
m robot Añadido: fr
Relación entre las principales clases de complejidad
Línea 4:
 
:el [[conjunto]] de los problemas de decisión que pueden ser resueltos por una máquina M utilizando [[Cota superior asintótica|O]](f(''n'')) del recurso R (donde ''n'' es el tamaño de la entrada).
 
==Relación entre las principales clases de complejidad==
La siguiente tabla muestra algunas de las clases de problemas (o lenguajes o gramáticas) que se consideran en teoría de la complejidad computacional. Cuando la clase '''X''' es un [[subconjunto]] estricto de '''Y''', '''X''' aparece en la tabla bajo '''Y''' con una línea sólida uniéndolos. Cuando es subconjunto pero no se sabe si es estricto, la línea es cortada y gris. Técnicamente hablando, el corte entre problemas decidibles e indecidibles es tema de la [[Teoría de la computabilidad]], pero resulta interesante mencionarlos aquí para poner en perspectiva las clases de complejidad
 
<table cellpadding="0" cellspacing="0" border="0" align="center">
<tr align="center">
<td colspan=2></td>
<td colspan=4><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Problema de decisión]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=2></td>
<td>[[image:solidLine.png]]</td>
<td colspan=2></td>
<td>[[image:solidLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Lenguaje recursivo enumerable]]</td></tr></table></td>
<td></td>
<td colspan=4><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Problema indecidible]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=3>[[image:solidLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Problema decidible]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=3>[[image:solidLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[EXPSPACE|ESPACIOEXP]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=3>[[image:dottedLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[EXPTIME|TIEMPOEXP]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=3>[[image:dottedLine.png]]</td>
</tr>
<tr align="center">
<td colspan=8><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[ESPACIOP]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[image:solidLine.png]]</td>
<td width=40>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr align="center">
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Gramática sensitiva al contexto]]</td></tr></table></td>
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td border="1">[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td colspan=1><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[ESPACIOP-completo]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[image:solidLine.png]]</td>
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr align="center">
<td>[[image:solidLine.png]]</td>
<td>[[image:solidLine.png]]</td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[Co-NP]]</td></tr></table></td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[NP]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[image:solidLine.png]]</td>
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr align="center">
<td>[[image:solidLine.png]]</td>
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[BPP]]</td></tr></table></td>
<td width=10></td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[BQP]]</td></tr></table></td>
<td width=10></td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[NP-completo]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[image:solidLine.png]]</td>
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr align="center">
<td>[[image:solidLine.png]]</td>
<td>[[image:solidLine.png]]</td>
<td colspan=6><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[P]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[image:solidLine.png]]</td>
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td colspan=4></td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr align="center">
<td>[[image:solidLine.png]]</td>
<td colspan=2><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[NC]]</td></tr></table></td>
<td colspan=4></td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"><tr><td align="center">[[P-completo]]</td></tr></table></td>
</tr>
<tr align="center">
<td>[[image:solidLine.png]]</td>
<td colspan=2>[[image:solidLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Gramática libre de contexto]]</td></tr></table></td>
</tr>
<tr align="center">
<td colspan=3>[[image:solidLine.png]]</td>
</tr>
<tr align="center">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%"><tr><td align="center">[[Gramática regular]]</td></tr></table></td>
</tr>
</table>
 
 
===Ejemplos===
Obtenido de «https://es.wikipedia.org/wiki/Clase_de_complejidad»