Lo siento si esto parece fuera de tema, los chicos de cstheory me dijeron era de tema allí y me envió aquí.
Algoritmo de Shor en un ordenador cuántico puede resolver un problema de factorización de enteros en tiempo Polinómico. Así que ¿por qué se considera este problema a no ser en P? ¿Hacer ordenadores cuánticos no cuenta? He mirado y ver una discusión sobre el asunto, pero no hay respuestas claras.
En definitiva, no cuentan los ordenadores cuánticos. Nos referimos muchos cuando decimos que algo está en P o NP de BPP, estantes. En particular, P significa que el problema puede ser resuelto por una máquina de Turing determinista en tiempo Polinómico. Ordenadores cuánticos no son ni determinista ni Turing.
Por esta razón factoring es en BQP, que es como el quantum de tiempo Polinómico.
El título de la pregunta es diferente de la cuestión del contenido. Desde la versión que le preguntó sobre cstheory es el que está en el título, voy a responder a eso.
El Factoring es tanto en $\mathsf{NP}$ $\mathsf{BQP}$ (polinomio tiempo cuántico TM). Esto no es extraño en absoluto, por ejemplo, cada problema en $\mathsf{P}$ es también en cada una de ellas. Estar en $\mathsf{NP}$ no significa que el problema es difícil, es un límite superior en la dificultad del problema. Un problema en $\mathsf{NP}$ puede ser arbitraria fácil. Supongo que usted está confuso $\mathsf{NP}$$\mathsf{NP\text{-}complete}$. No se sabe (de hecho es muy poco probable) que el Factoring es $\mathsf{NP\text{-}complete}$.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
