¡Más rápido que el navegador!
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.
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.
¡Nuevo!!: NP (clase de complejidad) y Algoritmo · Ver más »
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.
¡Nuevo!!: NP (clase de complejidad) y Camino hamiltoniano · 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!!: NP (clase de complejidad) y Ciencias de la computación · Ver más »
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.
¡Nuevo!!: NP (clase de complejidad) y Clases de complejidad P y NP · Ver más »
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.
¡Nuevo!!: NP (clase de complejidad) 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!!: NP (clase de complejidad) y Co-NP · Ver más »
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.
¡Nuevo!!: NP (clase de complejidad) y Forma normal conjuntiva · Ver más »
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.
¡Nuevo!!: NP (clase de complejidad) e Idioma inglés · 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!!: NP (clase de complejidad) y Máquina de Turing · 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!!: NP (clase de complejidad) 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!!: NP (clase de complejidad) 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 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.
¡Nuevo!!: NP (clase de complejidad) y P (clase de complejidad) · Ver más »
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.
¡Nuevo!!: NP (clase de complejidad) y PDF · 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!!: NP (clase de complejidad) y Problema de decisión · 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!!: NP (clase de complejidad) 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, 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.
¡Nuevo!!: NP (clase de complejidad) y Problema del viajante · 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!!: NP (clase de complejidad) y PSPACE · Ver más »
Stephen Cook
Stephen Arthur Cook (1939, Búfalo (Nueva York)) es un reconocido científico de la computación.
¡Nuevo!!: NP (clase de complejidad) y Stephen Cook · Ver más »
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.
¡Nuevo!!: NP (clase de complejidad) y Teoría de grafos · 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!!: NP (clase de complejidad) y Teoría de la complejidad computacional · 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!!: NP (clase de complejidad) y Teorema de Cook · Ver más »
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.
¡Nuevo!!: NP (clase de complejidad) y Test de primalidad · Ver más »
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.
¡Nuevo!!: NP (clase de complejidad) y Vértice (teoría de grafos) · Ver más »
2002
2002 fue un año común comenzado en martes, y terminado en martes, según el calendario gregoriano.
¡Nuevo!!: NP (clase de complejidad) y 2002 · Ver más »
2004
2004 fue un año bisiesto comenzado en jueves según el calendario gregoriano.
¡Nuevo!!: NP (clase de complejidad) y 2004 · Ver más »
Redirecciona aquí:
NP (Complejidad computacional), NP (complejidad computacional).
