Logo
Unionpedia
Comunicación
Disponible en Google Play
¡Nuevo! ¡Descarga Unionpedia en tu dispositivo Android™!
Gratis
¡Más rápido que el navegador!
 

Clases de complejidad P y NP

Índice Clases de complejidad P y NP

La relación entre las clases de complejidad NP y P es una pregunta que la teoría de la complejidad computacional aún no ha podido responder.

39 relaciones: Algoritmo, Algoritmo de Dijkstra, Algoritmo determinista, Axioma, Cadena de caracteres, Camino hamiltoniano, Ciclo euleriano, Ciencias de la computación, Clase de complejidad, Computación paralela, Cota superior asintótica, Dólar estadounidense, EXPTIME, FNP (clase de complejidad), FP (clase de complejidad), Instituto Clay de Matemáticas, Lisp, Máquina de Turing, Número entero, NP (clase de complejidad), NP-completo, NP-hard, P (clase de complejidad), P-completo, Pascal (lenguaje de programación), Problema de decisión, Problema de la suma de subconjuntos, Problema de satisfacibilidad booleana, Problema del viajante, Problemas del milenio, PSPACE, Stephen Cook, Subconjunto, Teoría de autómatas, Teoría de la complejidad computacional, Teoría de la computabilidad, Teoría de la computación, Teorema de Cook, Toroide.

Algoritmo

En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas, un algoritmo (del griego y latín, dixit algorithmus y este del griego arithmos, que significa «número», quizá también con influencia del nombre del matemático persa Al-Juarismi)1​ es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite llevar a cabo una actividad mediante pasos sucesivos que permitan la resolución o la toma de decisiones, de un problema, que pueden ser incluso  situaciones de nuestra vida cotidiana. Algunos ejemplos son los manuales de usuario, que muestran algoritmos para usar un aparato, o las instrucciones que recibe un trabajador de su patrón.

¡Nuevo!!: Clases de complejidad P y NP y Algoritmo · Ver más »

Algoritmo de Dijkstra

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tiene pesos en cada arista.

¡Nuevo!!: Clases de complejidad P y NP y Algoritmo de Dijkstra · Ver más »

Algoritmo determinista

En ciencias de la computación, un algoritmo determinista es un algoritmo que, en términos informales, es completamente predictivo si se conocen sus entradas.

¡Nuevo!!: Clases de complejidad P y NP y Algoritmo determinista · Ver más »

Axioma

Un axioma es una proposición asumida dentro de un cuerpo teórico sobre la cual descansan otros razonamientos y proposiciones deducidas de esas premisas.

¡Nuevo!!: Clases de complejidad P y NP y Axioma · Ver más »

Cadena de caracteres

En programación, una cadena de caracteres, palabras, ristra de caracteres o frase (string, en inglés) es una secuencia ordenada (de longitud arbitraria, aunque finita) de elementos que pertenecen a un cierto lenguaje formal o alfabeto análogas a una fórmula o a una oración.

¡Nuevo!!: Clases de complejidad P y NP y Cadena de caracteres · Ver más »

Camino hamiltoniano

Un camino hamiltoniano, en el campo matemático de la teoría de grafos, es un camino de un grafo, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez.

¡Nuevo!!: Clases de complejidad P y NP y Camino hamiltoniano · Ver más »

Ciclo euleriano

En la teoría de grafos, un camino euleriano es un camino que pasa por cada arista una y solo una vez.

¡Nuevo!!: Clases de complejidad P y NP y Ciclo euleriano · Ver más »

Ciencias de la computación

Las Ciencias de la computación estudian los fundamentos teóricos de la información y el cómputo, junto con técnicas prácticas para la implementación y aplicación de estos fundamentos teóricos.

¡Nuevo!!: Clases de complejidad P y NP y Ciencias de la computación · Ver más »

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.

¡Nuevo!!: Clases de complejidad P y NP y Clase de complejidad · Ver más »

Computación paralela

La computación paralela es una forma de cómputo en la que muchas instrucciones se ejecutan simultáneamente, operando sobre el principio de que problemas grandes, a menudo se pueden dividir en unos más pequeños, que luego son resueltos simultáneamente (en paralelo).

¡Nuevo!!: Clases de complejidad P y NP y Computación paralela · Ver más »

Cota superior asintótica

En análisis de algoritmos una cota superior asintótica es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito.

¡Nuevo!!: Clases de complejidad P y NP y Cota superior asintótica · Ver más »

Dólar estadounidense

El dólar estadounidense es la moneda oficial de Estados Unidos de América.

¡Nuevo!!: Clases de complejidad P y NP y Dólar estadounidense · Ver más »

EXPTIME

En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2p(n)), donde p(n) es una función polinomial sobre n. En términos de DTIME, Se sabe que y por el teorema de la jerarquía temporal: de manera que al menos una de las inclusiones de la primera línea debe ser estricta (se piensa que todas esas inclusiones son estrictas).

¡Nuevo!!: Clases de complejidad P y NP y EXPTIME · Ver más »

FNP (clase de complejidad)

En complejidad computacional, FNP (function NP o NP funcional) es la clase de complejidad que extiende la clase NP (la cual incluye exclusivamente problemas de decisión), hacia problemas computacionales de tipo funcional, es decir, aquellos que obtienen como salidas valores distintos de SÍ o NO.

¡Nuevo!!: Clases de complejidad P y NP y FNP (clase de complejidad) · Ver más »

FP (clase de complejidad)

En complejidad computacional, FP ("function P" o "P funcional") es la clase de complejidad que extiende la clase P (la cual incluye exclusivamente problemas de decisión), hacia problemas computacionales de tipo funcional, es decir, aquellos que obtienen como salidas valores distintos de SÍ o NO.

¡Nuevo!!: Clases de complejidad P y NP y FP (clase de complejidad) · Ver más »

Instituto Clay de Matemáticas

El Instituto Clay de Matemáticas (inglés Clay Mathematics Institute o CMI) es una fundación sin fines de lucro de Cambridge, Massachusetts, dedicada a incrementar y diseminar el conocimiento matemático.

¡Nuevo!!: Clases de complejidad P y NP e Instituto Clay de Matemáticas · Ver más »

Lisp

Lisp (históricamente LISP) es una familia de lenguajes de programación de computadora de tipo multiparadigma con larga historia y una inconfundible y útil sintaxis basada en la notación polaca.

¡Nuevo!!: Clases de complejidad P y NP y Lisp · 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 a una tabla de reglas.

¡Nuevo!!: Clases de complejidad P y NP y Máquina de Turing · Ver más »

Número entero

Un número entero es un elemento del conjunto numérico que contiene los números naturales \mathbb.

¡Nuevo!!: Clases de complejidad P y NP y Número entero · Ver más »

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").

¡Nuevo!!: Clases de complejidad P y NP y NP (clase de complejidad) · Ver más »

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.

¡Nuevo!!: Clases de complejidad P y NP y NP-completo · Ver más »

NP-hard

En teoría de la complejidad computacional, la clase de complejidad NP-hard (o NP-complejo, o NP-difícil) es el conjunto de los problemas de decisión que contiene los problemas H tales que todo problema L en NP puede ser transformado polinomialmente en H. Esta clase puede ser descrita como aquella que contiene a los problemas de decisión que son como mínimo tan difíciles como un problema de NP.

¡Nuevo!!: Clases de complejidad P y NP y NP-hard · Ver más »

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 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.

¡Nuevo!!: Clases de complejidad P y NP y P (clase de complejidad) · Ver más »

P-completo

En teoría de la complejidad computacional, la clase de complejidad P-completo es un conjunto de problemas de decisión de gran utilidad para identificar los problemas que pueden ser resueltos eficientemente en máquinas paralelas.

¡Nuevo!!: Clases de complejidad P y NP y P-completo · Ver más »

Pascal (lenguaje de programación)

Pascal es un lenguaje creado por el profesor suizo Niklaus Wirth entre los años 1968 y 1969 y publicado en 1970.

¡Nuevo!!: Clases de complejidad P y NP y Pascal (lenguaje de programación) · 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!!: Clases de complejidad P y NP y Problema de decisión · Ver más »

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.

¡Nuevo!!: Clases de complejidad P y NP y Problema de la suma de subconjuntos · Ver más »

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.

¡Nuevo!!: Clases de complejidad P y NP y Problema de satisfacibilidad booleana · Ver más »

Problema del viajante

El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-duro dentro en la optimización combinatoria, muy importante en la investigación de operaciones y en la ciencia de la computación.

¡Nuevo!!: Clases de complejidad P y NP y Problema del viajante · Ver más »

Problemas del milenio

Los problemas del milenio son siete problemas matemáticos cuya resolución sería premiada, según anunció el Clay Mathematics Institute en el año 2000, con la suma de un millón de dólares cada uno.

¡Nuevo!!: Clases de complejidad P y NP y Problemas del milenio · Ver más »

PSPACE

En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio de polinomios (S(n).

¡Nuevo!!: Clases de complejidad P y NP y PSPACE · Ver más »

Stephen Cook

Stephen Arthur Cook (1939, Buffalo, Nueva York) es un reconocido científico de la computación.

¡Nuevo!!: Clases de complejidad P y NP y Stephen Cook · Ver más »

Subconjunto

En las matemáticas, un conjunto es subconjunto de un conjunto si «está contenido» dentro de.

¡Nuevo!!: Clases de complejidad P y NP y Subconjunto · Ver más »

Teoría de autómatas

La teoría de autómatas es una rama de la teoría de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver.

¡Nuevo!!: Clases de complejidad P y NP y Teoría de autómatas · Ver más »

Teoría de la complejidad computacional

La teoría de la complejidad computacional 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!!: Clases de complejidad P y NP y Teoría de la complejidad computacional · Ver más »

Teoría de la computabilidad

La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con la llamada máquina de Turing.

¡Nuevo!!: Clases de complejidad P y NP y Teoría de la computabilidad · Ver más »

Teoría de la computación

La teoría de la computación es un conjunto de conocimientos racionales, sistematizados y funcionales que se centran en el estudio de la abstracción de los procesos que ocurren en la realidad con el fin de reproducirlos con ayuda de sistemas formales, es decir, a través de códigos de caracteres e instrucciones lógicas, reconocibles por el ser humano, con capacidad de ser modeladas en las limitaciones de dispositivos que procesan información y que efectúan cálculos como, por ejemplo, el ordenador.

¡Nuevo!!: Clases de complejidad P y NP y Teoría de la computación · Ver más »

Teorema de Cook

En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente: Cook demostró este teorema en su artículo de 1971 "The Complexity of Theorem Proving Procedures".

¡Nuevo!!: Clases de complejidad P y NP y Teorema de Cook · Ver más »

Toroide

En geometría el toroide o toro es la superficie de revolución generada por una curva plana cerrada simple que gira alrededor de una recta exterior coplanar (el eje de rotación) con la que no se interseca.

¡Nuevo!!: Clases de complejidad P y NP y Toroide · Ver más »

Redirecciona aquí:

Clases de complejidad p y np, P = NP, P versus NP, P-NP, P=NP, Problema P - NP, Problema P = NP, Problema P-NP, Problema P=NP, Problema ¿P=NP?.

SalienteEntrante
¡Hey! ¡Ahora tenemos Facebook! »