Similitudes entre Clases de complejidad P y NP y NP-hard
Clases de complejidad P y NP y NP-hard tienen 9 cosas en común (en Unionpedia): Algoritmo, Clase de complejidad, NP (clase de complejidad), NP-completo, P (clase de complejidad), Problema de decisión, Problema de la suma de subconjuntos, Problema de satisfacibilidad booleana, Teoría de la complejidad computacional.
Algoritmo
En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas, un algoritmo (probablemente del latín tardío algorithmus, y este del árabe clásico ḥisābu lḡubār, que significa «cálculo mediante cifras arábigas») es un conjunto de instrucciones o reglas definidas y no-ambiguas, ordenadas y finitas que permite, típicamente, solucionar un problema, realizar un cómputo, procesar datos y llevar a cabo otras tareas o actividades.
Algoritmo y Clases de complejidad P y NP · Algoritmo y NP-hard ·
Clase de complejidad
En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada.
Clase de complejidad y Clases de complejidad P y NP · Clase de complejidad y NP-hard ·
NP (clase de complejidad)
En teoría de la complejidad computacional, NP es el acrónimo en inglés de nondeterministic polynomial time ("tiempo polinomial no determinista").
Clases de complejidad P y NP y NP (clase de complejidad) · NP (clase de complejidad) y NP-hard ·
NP-completo
En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo.
Clases de complejidad P y NP y NP-completo · NP-completo y NP-hard ·
P (clase de complejidad)
En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor o igual que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico o polinomial P. La tesis de Cobham postula que la clase P es la que tiene los problemas tratables más grandes, es decir, los problemas de gran tamaño que se pueden calcular de forma eficiente con un ordenador.
Clases de complejidad P y NP y P (clase de complejidad) · NP-hard y P (clase de complejidad) ·
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.
Clases de complejidad P y NP y Problema de decisión · NP-hard y Problema de decisión ·
Problema de la suma de subconjuntos
El problema de la suma de subconjuntos es un problema importante en la teoría de la complejidad y en la criptografía.
Clases de complejidad P y NP y Problema de la suma de subconjuntos · NP-hard y Problema de la suma de subconjuntos ·
Problema de satisfacibilidad booleana
En teoría de la complejidad computacional, el Problema de satisfacibilidad booleana (también llamado SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP-completo.
Clases de complejidad P y NP y Problema de satisfacibilidad booleana · NP-hard y Problema de satisfacibilidad booleana ·
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.
Clases de complejidad P y NP y Teoría de la complejidad computacional · NP-hard y Teoría de la complejidad computacional ·
La lista de arriba responde a las siguientes preguntas
- En qué se parecen Clases de complejidad P y NP y NP-hard
- Qué tienen en común Clases de complejidad P y NP y NP-hard
- Semejanzas entre Clases de complejidad P y NP y NP-hard
Comparación de Clases de complejidad P y NP y NP-hard
Clases de complejidad P y NP tiene 44 relaciones, mientras NP-hard tiene 13. Como tienen en común 9, el índice Jaccard es 15.79% = 9 / (44 + 13).
Referencias
En este artículo se encuentra la relación entre Clases de complejidad P y NP y NP-hard. Si desea acceder a cada artículo del que se extrajo la información visite: