sospecha que muchas clases de complejidad conocidas son desiguales
question: ¿Cuál es la suposición no probada generalmente atribuida al valor de las 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.
¿Cuál es la suposición no probada generalmente atribuida al valor de las clases de complejidad?
Se sospecha que muchas clases de complejidad conocidas son desiguales , pero esto no ha sido probado.
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.
Se <hl> sospecha que muchas clases de complejidad conocidas son desiguales <hl> , pero esto no ha sido probado.
Se <hl> sospecha que muchas clases de complejidad conocidas son desiguales <hl>, 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.
<hl> Se sospecha que muchas clases de complejidad conocidas son desiguales , pero esto no ha sido probado. <hl> 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.