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

Clases de complejidad P y NP

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

47 relaciones: Algoritmo, Algoritmo de Dijkstra, Algoritmo determinista, Axioma, Cadena de caracteres, Camino hamiltoniano, Charles E. Leiserson, Christos Papadimitriou, Ciclo euleriano, Ciencias de la computación, Clase de complejidad, Clifford Stein, Clique, Co-NP, Computación paralela, Cota superior asintótica, Dólar estadounidense, EXPTIME, FNP (clase de complejidad), FP (clase de complejidad), Instituto Clay de Matemáticas, Introducción a los algoritmos, Lisp, Máquina de Turing, Número entero, Neil Immerman, NP (clase de complejidad), NP-completo, NP-hard, 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, Ronald Rivest, 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, Thomas H. Cormen, Tiempo polinómico, 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 a su vez del matemático persa Al-Juarismi) es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite llevar a cabo una actividad mediante pasos sucesivos que no generen dudas a quien deba hacer dicha actividad.

¡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 al resto de los vértices en un grafo con 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 esos razonamientos.

¡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 »

Charles E. Leiserson

Charles E. Leiserson (10 de noviembre de 1953), es un científico informático estadounidense, especializado en la teoría de computación paralela y computación distribuida, y particularmente en sus aplicaciones prácticas.

¡Nuevo!!: Clases de complejidad P y NP y Charles E. Leiserson · Ver más »

Christos Papadimitriou

Christos Papadimitriou es un profesor de la división de ciencias de la computación en la Universidad de California, Berkeley.

¡Nuevo!!: Clases de complejidad P y NP y Christos Papadimitriou · 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 »

Clifford Stein

Clifford Stein es catedrático de informática en la universidad de Columbia, en Nueva York.

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

Clique

En teoría de grafos, un clique en un grafo no dirigido G es un conjunto de vértices V tal que para todo par de vértices de V, existe una arista que las conecta.

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

Co-NP

En teoría de la complejidad computacional, la clase de complejidad co-NP es el conjunto de los problemas de decisión complementarios a los de la clase NP.

¡Nuevo!!: Clases de complejidad P y NP y Co-NP · 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.

¡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 »

Introducción a los algoritmos

Introducción a los algoritmos (Introduction to Algorithms en versión original) es un libro de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein.

¡Nuevo!!: Clases de complejidad P y NP e Introducción a los algoritmos · Ver más »

Lisp

El Lisp (o LISP) es una familia de lenguajes de programación de computadora de tipo multiparadigma con una larga historia y una sintaxis completamente entre paréntesis.

¡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

Los números enteros son un conjunto numérico que contiene los números naturales, sus inversos aditivos y el cero.

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

Neil Immerman

Neil Immerman es un informático teórico estadounidense, profesor de ciencias de la computación en la Universidad Amherst Massachusetts.

¡Nuevo!!: Clases de complejidad P y NP y Neil Immerman · 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 »

Pascal (lenguaje de programación)

Pascal es un lenguaje de programación desarrollado 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 Agente Viajero (TSP por sus siglas en inglés) o problema del viajante, 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 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 »

Ronald Rivest

Ronald Linn Rivest (6 de mayo de 1947) es un criptógrafo y profesor en el MIT.

¡Nuevo!!: Clases de complejidad P y NP y Ronald Rivest · 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 las ciencias 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 a 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 »

Thomas H. Cormen

Thomas H. Cormen es catedrático de informática en la universidad Dartmouth.

¡Nuevo!!: Clases de complejidad P y NP y Thomas H. Cormen · Ver más »

Tiempo polinómico

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 Tiempo polinómico · Ver más »

Toroide

En geometría el toroide 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, Problema P = NP, Problema ¿P=NP?.

SalienteEntrante
¡Hey! ¡Ahora tenemos Facebook! »