Sobre clases de complejidad

[Livilro]

"De esto, parece evidente que si un problema A se puede reducir a otro problema B, entonces B es igual o más complicado que A. Dicho de otra manera, la reducción de un problema en otro no puede hacerlo más facil."


A eso voy, conociendo eso y que:


" la entropía, también llamada entropía de la información y entropía de Shannon mide la incertidumbre de una fuente de información."


Siendo dichas fuentes los mismos problemas P y NP ¿ no sería un valor de entropía de Shanon lo que estaría aumentando al reducir el problema ?

[pod]

Saludos Pod eso entiendo por complejidad, no hay mucha duda,
ese párrafo esta muy claro.




P puedo tratarlo como conjunto de diferentes problemas {p1,p2,..}
¿es incorrecto ?, ¿ es lo que refieres con p ∈ P no ?

Por ello asumí A y B como conjuntos,
y perdón...obvié nombrar que la complejidad es en p ∈ P.

Traté tambien a NP como conjunto para enfrentarlos.

Creo que éste no es el hilo adecuado para debatir la diferencia entre un conjunto y sus elementos.

Algo tan ambigüo como P y NP, (problemas...será por variedad..)

P y NP no son ambiguos. Ambos conjuntos tienen una definición matemática precisa:

Un problema es NP si, dada una solución candidata, existe un algoritmo que se ejecuta en tiempo polinómico para comprobar si dicha solución es válida o no.

Un problema es P si existe un algoritmo que se ejecuta en tiempo polinómico que permite encontrar una solución válida (sin partir de nada más).

y además nombrando una complejidad intrinseca de los mismos sea lo que sea esa complejidad intrinseca,

En realidad, ahí solemos cometer un pequeño abuso de lenguaje. Lo que tiene una complejidad bien definida es un algoritmo (se suele definir la complejidad de un algoritmo con la notación "gran-O"). Por extensión, decimos que la complejidad de un problema es igual a la complejidad del mejor algoritmo capaz de encontrar una solución. Por ejemplo, se puede demostrar matemáticamente que no existe ningún algoritmo que, en general, pueda ordenar N números en un tiempo mejor que $O(N \log N)$. Por eso, decimos que el problema de la ordenación tiene complejidad $O(N \log N)$ (nótese que $O(N \log N) < O(N^2)$, o sea que la complejidad de este problema está acotada por un polinomio, en conclusión el problema de la ordenación pertenece a P... y como puedo comprobar si una lista está ordenada en tiempo O(N), entonces trivialmente también pertenece a NP).

entiendo con ello que un problema es reductible "si y solo si" la complejidad (dije condiciones pensando en conjuntos todo el tiempo) se mantuviese igual o aumentase para el problema reducido, nunca que dusminuyese.

Que un problema sea más complejo que otro es condición necesaria para que pueda haber una reducción, pero no suficiente. Así que no es "sí y sólo sí".


clara como el agua esa parte.

Algo mas complejo quiero pensar que tenga mas condiciones en la formulación que algo menos complejo.

No tiene por qué.

Obviamente la complejidad no es un parámetro pero si esta define a los conjuntos de problemas y establece rangos entre ellos puedo usarla a mi favor como un parámetro no ?

No le encuentro sentido a ello, la verdad.

(Analizaba entropía de Shanon y un supuesto parámetro complejidad.)

Intentar mezclar conceptos tan poco relacionados no parece facilitar la comprensión del asunto. Te agradecería que mantuvieras el tema del hilo sin desviarlo.