Tabla de contenidos
25 relaciones: Algoritmo, Camino hamiltoniano, Ciencias de la computación, Clases de complejidad P y NP, Clique, Co-NP, Forma normal conjuntiva, Idioma inglés, Máquina de Turing, NP-completo, NP-hard, P (clase de complejidad), PDF, Problema de decisión, Problema de satisfacibilidad booleana, Problema del viajante, PSPACE, Stephen Cook, Teoría de grafos, Teoría de la complejidad computacional, Teorema de Cook, Test de primalidad, Vértice (teoría de grafos), 2002, 2004.
- Clases de complejidad
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.
Ver NP (clase de complejidad) y Algoritmo
Camino hamiltoniano
En teoría de grafos, un camino hamiltoniano en un grafo es un camino (es decir, una sucesión de aristas adyacentes), que visita todos los vértices del grafo una sola vez.
Ver NP (clase de complejidad) y Camino hamiltoniano
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.
Ver NP (clase de complejidad) y Ciencias de la computación
Clases de complejidad P y NP
La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder.
Ver NP (clase de complejidad) y Clases de complejidad P y NP
Clique
En teoría de grafos, un clique (o «una clique», pronunciado /klik/), a veces traducido desde el inglés como clan o camarilla, C, en un grafo no dirigido es un conjunto de vértices,, tal que todo par de vértices distintos son adyacentes, es decir, existe una arista que los conecta.
Ver NP (clase de complejidad) y Clique
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. NP (clase de complejidad) y co-NP son clases de complejidad.
Ver NP (clase de complejidad) y Co-NP
Forma normal conjuntiva
En lógica booleana, una fórmula está en forma normal conjuntiva (FNC) si corresponde a una conjunción de cláusulas, donde una cláusula es una disyunción de literales, donde un literal y su complemento no pueden aparecer en la misma cláusula.
Ver NP (clase de complejidad) y Forma normal conjuntiva
Idioma inglés
El idioma inglés (English) es una lengua germánica occidental perteneciente a la familia de lenguas indoeuropeas, que surgió en los reinos anglosajones de Inglaterra.
Ver NP (clase de complejidad) e Idioma inglé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.
Ver NP (clase de complejidad) y Máquina de Turing
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. NP (clase de complejidad) y nP-completo son clases de complejidad.
Ver NP (clase de complejidad) y NP-completo
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. NP (clase de complejidad) y nP-hard son clases de complejidad.
Ver NP (clase de complejidad) 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. NP (clase de complejidad) y p (clase de complejidad) son clases de complejidad.
Ver NP (clase de complejidad) y P (clase de complejidad)
PDF (siglas en inglés de Portable Document Format, 'formato de documento portátil') es un formato de almacenamiento para documentos digitales independientes de plataformas de software o hardware.
Ver NP (clase de complejidad) y PDF
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.
Ver NP (clase de complejidad) y Problema de decisión
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.
Ver NP (clase de complejidad) y Problema de satisfacibilidad booleana
Problema del viajante
El problema del vendedor viajero (problema del vendedor ambulante, problema del agente viajero o problema del viajante, PCP, TSP por sus siglas en inglés, Travelling Salesman Problem) 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-Hard dentro en la optimización combinatoria, muy importante en investigación operativa y en ciencias de la computación.
Ver NP (clase de complejidad) y Problema del viajante
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). NP (clase de complejidad) y PSPACE son clases de complejidad.
Ver NP (clase de complejidad) y PSPACE
Stephen Cook
Stephen Arthur Cook (1939, Búfalo (Nueva York)) es un reconocido científico de la computación.
Ver NP (clase de complejidad) y Stephen Cook
Teoría de grafos
La teoría de grafos, también llamada teoría de gráficas, es una rama de la matemática y las ciencias de la computación que estudia las propiedades de los grafos.
Ver NP (clase de complejidad) y Teoría de grafos
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.
Ver NP (clase de complejidad) y Teoría de la complejidad computacional
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".
Ver NP (clase de complejidad) y Teorema de Cook
Test de primalidad
La cuestión de la determinación de si un número n dado es primo es conocida como el problema de la primalidad.
Ver NP (clase de complejidad) y Test de primalidad
Vértice (teoría de grafos)
En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos.
Ver NP (clase de complejidad) y Vértice (teoría de grafos)
2002
2002 fue un año común comenzado en martes, y terminado en martes, según el calendario gregoriano.
Ver NP (clase de complejidad) y 2002
2004
2004 fue un año bisiesto comenzado en jueves según el calendario gregoriano.
Ver NP (clase de complejidad) y 2004
Ver también
Clases de complejidad
- ALL (clase de complejidad)
- Clase de complejidad
- Co-NP
- Co-NP-completo
- DSPACE
- DTIME
- E (clase de complejidad)
- ELEMENTARY
- ESPACE
- EXPSPACE
- EXPTIME
- Esquema de aproximación de tiempo polinómico
- FNP (clase de complejidad)
- FP (clase de complejidad)
- Jerarquía aritmética
- Jerarquía polinómica
- L (clase de complejidad)
- LOGCFL
- NC (clase de complejidad)
- NEXPTIME
- NL (clase de complejidad)
- NP (clase de complejidad)
- NP-completo
- NP-equivalente
- NP-hard
- NSPACE
- NTIME
- P (clase de complejidad)
- P-completo
- P/poly
- PH (clase de complejidad)
- PR (complejidad)
- PSPACE
- PSPACE-completo
- PolyL
- R (clase de complejidad)
- RE (clase de complejidad)
- SC (clase de complejidad)
- SL (clase de complejidad)
- TFNP
- Tiempo pseudopolinómico
- Totalmente NP-completo
- UP (clase de complejidad)
También se conoce como NP (Complejidad computacional).