P NP NP
question: ¿Qué es una expresión que se puede utilizar para ilustrar la presunta desigualdad de clases de complejidad?, context: Se sospecha que muchas clases de complejidad conocidas son desiguales, pero esto no ha sido probado. Por ejemplo P NP NP. PP PSPSPACE, pero es posible que P = PSPACE. Si P no es igual a NP, entonces P tampoco es igual a PSPACE. Dado que hay muchas clases de complejidad conocidas entre P y PSPACE, como RP, BPP, PP, BQP, MA, PH, etc., es posible que todas estas clases de complejidad colapsen a una clase. Probar que cualquiera de estas clases es desigual sería un gran avance en la teoría de la complejidad.
¿Qué es una expresión que se puede utilizar para ilustrar la presunta desigualdad de clases de complejidad?
Por ejemplo P NP NP .
Se sospecha que muchas clases de complejidad conocidas son desiguales, pero esto no ha sido probado. Por ejemplo P NP NP. PP PSPSPACE, pero es posible que P = PSPACE. Si P no es igual a NP, entonces P tampoco es igual a PSPACE. Dado que hay muchas clases de complejidad conocidas entre P y PSPACE, como RP, BPP, PP, BQP, MA, PH, etc., es posible que todas estas clases de complejidad colapsen a una clase. Probar que cualquiera de estas clases es desigual sería un gran avance en la teoría de la complejidad.
Por ejemplo <hl> P NP NP <hl> .
Se sospecha que muchas clases de complejidad conocidas son desiguales, pero esto no ha sido probado. Por ejemplo <hl> P NP NP <hl>. PP PSPSPACE, pero es posible que P = PSPACE. Si P no es igual a NP, entonces P tampoco es igual a PSPACE. Dado que hay muchas clases de complejidad conocidas entre P y PSPACE, como RP, BPP, PP, BQP, MA, PH, etc., es posible que todas estas clases de complejidad colapsen a una clase. Probar que cualquiera de estas clases es desigual sería un gran avance en la teoría de la complejidad.
Se sospecha que muchas clases de complejidad conocidas son desiguales, pero esto no ha sido probado. <hl> Por ejemplo P NP NP . <hl> PP PSPSPACE, pero es posible que P = PSPACE. Si P no es igual a NP, entonces P tampoco es igual a PSPACE. Dado que hay muchas clases de complejidad conocidas entre P y PSPACE, como RP, BPP, PP, BQP, MA, PH, etc., es posible que todas estas clases de complejidad colapsen a una clase. Probar que cualquiera de estas clases es desigual sería un gran avance en la teoría de la complejidad.