PP (clase de complejidad)

En teoría de la complejidad computacional PP, que quiere decir tiempo polinomial probabilístico, es una clase de problema de decisión resoluble por una máquina de Turing probabilística (diferente de la máquina de Turing general o determinista, en que las transiciones entre estados tienen la misma probabilidad de ocurrencia) con un error de probabilidad de menos de 1/2 para todas las instancias.

6 relaciones: Cuerpo finito, Máquina de Turing, Máquina de Turing probabilística, Problema de decisión, Teoría de la complejidad computacional, Test de Solovay-Strassen.

Cuerpo finito

En matemáticas y, más precisamente, en álgebra abstracta, un cuerpo finito, campo finito o campo de Galois (llamado así por Évariste Galois) es un cuerpo con un número finito de elementos.

¡Nuevo!!: PP (clase de complejidad) y Cuerpo finito · Ver más »

Máquina de Turing

Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas.

¡Nuevo!!: PP (clase de complejidad) y Máquina de Turing · Ver más »

Máquina de Turing probabilística

En Teoría de la complejidad computacional, se utilizan Máquinas de Turing probabilísticas para definir diferentes clases de complejidad.

¡Nuevo!!: PP (clase de complejidad) y Máquina de Turing probabilística · Ver más »

Problema de decisión

En teoría de la computación, un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita.

¡Nuevo!!: PP (clase de complejidad) y Problema de decisión · Ver más »

Teoría de la complejidad computacional

La teoría de la complejidad computacional o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad.

¡Nuevo!!: PP (clase de complejidad) y Teoría de la complejidad computacional · Ver más »

Test de Solovay-Strassen

El test de primalidad de Solovay-Strassen, creado por Robert M. Solovay y Volker Strassen en 1977, es un test de primalidad probabilístico.

¡Nuevo!!: PP (clase de complejidad) y Test de Solovay-Strassen · Ver más »

Unionpedia es un mapa conceptual o red semántica organizado en forma de enciclopedia – diccionario. Otorga una breve definición de cada concepto y las de todos sus relacionados.

Es un mapa mental online gigante que sirve como base para crear diagramas de conceptos, cuadros sinópticos o de síntesis. Es gratuito – gratis, de uso libre y cada artículo o documento se puede descargar. Es una herramienta, recurso o referencia de estudio, investigación, para la educación, aprendizaje o enseñanza, que pueden utilizar docentes, maestros, profesores, educadores, alumnos o estudiantes; para el mundo académico o escolar: para la escuela, primaria, secundaria, media, colegio, tecnicatura, facultad, universidad, carreras de grado, maestrías o doctorados; para trabajos, informes, monografías, proyectos, ideas, documentación, resúmenes, relevamientos o tesis. Aquí aparece la definición, explicación, descripción, o el significado de cada significante sobre el que necesites información, y una lista o listado de sus conceptos asociados en forma de glosario. Disponible en español, inglés, portugués, japonés, chino, francés, alemán, italiano, polaco, holandés, ruso, árabe, hindi, sueco, ucraniano, húngaro, catalán, checo, hebreo, danés, finlandés, indonesio, noruego, rumano, turco, vietnamita, coreano, tailandés, griego, búlgaro, croata, eslovaco, lituano, filipino, letón, estonio y esloveno. Más idiomas próximamente.

Toda la información fue extraída de Wikipedia, y está disponible bajo la Licencia Creative Commons Atribución Compartir Igual 3.0.

Unionpedia no está respaldada por ni afiliada a la Fundación Wikimedia.

Google Play, Android y el logotipo de Google Play son marcas comerciales de Google Inc.

Política de privacidad