Tweet
x ∈ A
p ∈ P
P = A
np ∈ NP
NP = B
Premisa añadida- "Por extensión, decimos que la complejidad de un problema es igual a la complejidad del mejor algoritmo capaz de encontrar una solución."
Implica poder hablar de "la complejidad de un problema" obviando tratarse finalmente de un algoritmo determinado y obviando ser este capaz de encontrar una solución.
Máxima complejidad (ideal) de un problema = ningún algoritmo capaz de encontrar solución.
P=NP si y solo si ( aunque se valoran mas condiciones ) la diferencia de complejidad entre ambos sea igual o mayor para el problema reducido, en este caso para NP(B),
ya que reducir de NP(B) a P(A) implica un aumento máximo de la complejidad al tomar la siguiente consideración para P(A) :
"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)"". "
(sin partir de nada mas)- se asume que el conjunto P(A) pueda contener elementos dados o cercanos a la irreductibilidad.
Valorando además,
"En matemáticas, y más especialmente en teoría de anillos, una no-unidad en un dominio de integridad se dice que es irreducible si esta no puede ser expresada como producto de dos no unidades. Equivalentemente, una no-unidad x es irreducible si x ≠ 0 y todo divisor d de x es un asociado de 1 o de x"
NP(B) no puede ser reducido a P(A) sin incurrir en una ambigüación ( perdida de información ) asociada al aumento máximo de la complejidad, siendo máxima esa perdida en el caso de querer llevar a NP(B) al límite de la irreductibilidad.
Esto implica no cumplir la definición clásica para P=NP(A=B) : " Dos conjuntos son iguales, expresado A = B, solamente cuando constan de los mismos elementos."
, para entrar en definiciones "relativistas" en función de la complejidad que los define al ser esta la única relación que siempre mantienen todos los problemas independientemente de los elementos que los formen,
clases de complejidad en todos los casos.
No nos encontramos en una situación de perfecta simetría al afrontar la pregunta ¿ P=NP , (A=B) ? si pudiendo conservar una proporcionalidad entre ambos durante procesos de 'aumento' o 'reducción' extremos.
Lo anterior solo es valorable considerando a P como conjunto de diferentes problemas p.
¿ Es errónea esa consideración ?
( el centro del hilo es esta pregunta, gracias )
Perdón por lo extenso y gracias por la información de la ordenación Pod, cambios en la ordenación de los elementos de un conjunto.
(Perdón por preguntar por la entropía de Shanon, se me hace díficil no meterla en esto incoscientemente...)
p ∈ P
P = A
np ∈ NP
NP = B
Premisa añadida- "Por extensión, decimos que la complejidad de un problema es igual a la complejidad del mejor algoritmo capaz de encontrar una solución."
Implica poder hablar de "la complejidad de un problema" obviando tratarse finalmente de un algoritmo determinado y obviando ser este capaz de encontrar una solución.
Máxima complejidad (ideal) de un problema = ningún algoritmo capaz de encontrar solución.
P=NP si y solo si ( aunque se valoran mas condiciones ) la diferencia de complejidad entre ambos sea igual o mayor para el problema reducido, en este caso para NP(B),
ya que reducir de NP(B) a P(A) implica un aumento máximo de la complejidad al tomar la siguiente consideración para P(A) :
"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)"". "
(sin partir de nada mas)- se asume que el conjunto P(A) pueda contener elementos dados o cercanos a la irreductibilidad.
Valorando además,
"En matemáticas, y más especialmente en teoría de anillos, una no-unidad en un dominio de integridad se dice que es irreducible si esta no puede ser expresada como producto de dos no unidades. Equivalentemente, una no-unidad x es irreducible si x ≠ 0 y todo divisor d de x es un asociado de 1 o de x"
NP(B) no puede ser reducido a P(A) sin incurrir en una ambigüación ( perdida de información ) asociada al aumento máximo de la complejidad, siendo máxima esa perdida en el caso de querer llevar a NP(B) al límite de la irreductibilidad.
Esto implica no cumplir la definición clásica para P=NP(A=B) : " Dos conjuntos son iguales, expresado A = B, solamente cuando constan de los mismos elementos."
, para entrar en definiciones "relativistas" en función de la complejidad que los define al ser esta la única relación que siempre mantienen todos los problemas independientemente de los elementos que los formen,
clases de complejidad en todos los casos.
No nos encontramos en una situación de perfecta simetría al afrontar la pregunta ¿ P=NP , (A=B) ? si pudiendo conservar una proporcionalidad entre ambos durante procesos de 'aumento' o 'reducción' extremos.
Lo anterior solo es valorable considerando a P como conjunto de diferentes problemas p.
¿ Es errónea esa consideración ?
( el centro del hilo es esta pregunta, gracias )
Perdón por lo extenso y gracias por la información de la ordenación Pod, cambios en la ordenación de los elementos de un conjunto.
(Perdón por preguntar por la entropía de Shanon, se me hace díficil no meterla en esto incoscientemente...)