Tabla de contenidos
44 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, Contraejemplo, 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, Máximo común divisor, 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, Raíz cuadrada, 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, Valor absoluto, Wiki.
- Conjeturas matemáticas
- Informática de 1956
- Introducciones relacionadas a la ciencia de la computación de 1956
- Optimización
- Problemas del milenio
- Problemas matemáticos no resueltos
- Problemas no resueltos de las ciencias de la computación
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 Clases de complejidad P y NP y Algoritmo
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.
Ver Clases de complejidad P y NP y Algoritmo de Dijkstra
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.
Ver Clases de complejidad P y NP y Algoritmo determinista
Axioma
Axioma es una proposición tan clara y evidente que se admite sin demostración.
Ver Clases de complejidad P y NP y Axioma
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.
Ver Clases de complejidad P y NP y Cadena de caracteres
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 Clases de complejidad P y NP y Camino hamiltoniano
Ciclo euleriano
En la teoría de grafos, un camino euleriano es un camino que pasa por cada arista una y solo una vez.
Ver Clases de complejidad P y NP y Ciclo euleriano
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 Clases de complejidad P y NP y Ciencias de la computación
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.
Ver Clases de complejidad P y NP y Clase de complejidad
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).
Ver Clases de complejidad P y NP y Computación paralela
Contraejemplo
En lógica, especialmente en sus aplicaciones en matemáticas y filosofía, un contraejemplo es una excepción a una regla general propuesta, es decir, un caso específico de la falsedad de una cuantificación universal (un "para todo").
Ver Clases de complejidad P y NP y Contraejemplo
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.
Ver Clases de complejidad P y NP y Cota superior asintótica
Dólar estadounidense
El dólar estadounidense o dólar americano (también abreviado con el símbolo $ o con su abreviatura alfabética estándar internacional USD) es la moneda de curso legal de Estados Unidos, sus dependencias y otros países.
Ver Clases de complejidad P y NP y Dólar estadounidense
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.
Ver Clases de complejidad P y NP y EXPTIME
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.
Ver Clases de complejidad P y NP y FNP (clase de complejidad)
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.
Ver Clases de complejidad P y NP y FP (clase de complejidad)
Instituto Clay de Matemáticas
El Instituto Clay de Matemáticas (CMI)(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.
Ver Clases de complejidad P y NP e Instituto Clay de Matemáticas
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 homoicónica basada en la notación polaca.
Ver Clases de complejidad P y NP y Lisp
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 Clases de complejidad P y NP y Máquina de Turing
Máximo común divisor
En las matemáticas, se define el máximo común divisor (mcd o m.c.d.) de dos o más números enteros al mayor número entero que los divide sin dejar residuo alguno.
Ver Clases de complejidad P y NP y Máximo común divisor
Número entero
Un número entero es un elemento del conjunto numérico que contiene los números naturales; que son \mathbb.
Ver Clases de complejidad P y NP y Número entero
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").
Ver Clases de complejidad P y NP y NP (clase de complejidad)
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 son optimización.
Ver Clases de complejidad P y NP 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.
Ver Clases de complejidad P y NP 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.
Ver Clases de complejidad P y NP y P (clase de complejidad)
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.
Ver Clases de complejidad P y NP y P-completo
Pascal (lenguaje de programación)
Pascal es un lenguaje de programación creado por el profesor suizo Niklaus Wirth entre los años 1968 y 1969, y publicado en 1970.
Ver Clases de complejidad P y NP y Pascal (lenguaje de programación)
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 Clases de complejidad P y NP 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.
Ver Clases de complejidad P y NP 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.
Ver Clases de complejidad P y NP 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 Clases de complejidad P y NP y Problema del viajante
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. Clases de complejidad P y NP y problemas del milenio son problemas matemáticos no resueltos.
Ver Clases de complejidad P y NP y Problemas del milenio
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).
Ver Clases de complejidad P y NP y PSPACE
Raíz cuadrada
En las matemáticas, la raíz cuadrada de un número x es aquel número y que al ser multiplicado por sí mismo da como resultado el valor x, es decir, cumple la ecuación y^2.
Ver Clases de complejidad P y NP y Raíz cuadrada
Stephen Cook
Stephen Arthur Cook (1939, Búfalo (Nueva York)) es un reconocido científico de la computación.
Ver Clases de complejidad P y NP y Stephen Cook
Subconjunto
es subconjunto de otro conjunto si todos los elementos de pertenecen también a. Decimos entonces que «está contenido» dentro de.
Ver Clases de complejidad P y NP y Subconjunto
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.
Ver Clases de complejidad P y NP y Teoría de autómatas
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 Clases de complejidad P y NP y Teoría de la complejidad computacional
Teoría de la computabilidad
La teoría de la computabilidad o teoría de la recursión es la parte de la computación que estudia los problemas de decisión que se pueden resolver con un algoritmo o equivalentemente con una máquina de Turing.
Ver Clases de complejidad P y NP y Teoría de la computabilidad
Teoría de la computación
La teoría de la computación o teoría de la informática es un conjunto de conocimientos racionales y sistematizados que se centran en el estudio de la abstracción de los procesos, con el fin de reproducirlos con ayuda de sistemas formales; es decir, a través de símbolos y reglas lógicas.
Ver Clases de complejidad P y NP y Teoría de la computación
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 Clases de complejidad P y NP y Teorema de Cook
Toroide
En geometría el toroide es la superficie de revolución generada por un polígono o una curva plana cerrada simple que gira alrededor de una recta exterior coplanar (el eje de rotación) con la que no se interseca.
Ver Clases de complejidad P y NP y Toroide
Valor absoluto
En matemáticas, el valor absoluto o móduloJean-Robert Argand, introductor del término módulo en 1806, ver:,, 5- y +5 igual a cinco y de un número real x, denotado por |x|, es el valor de x sin considerar el signo, sea este positivo o negativo.
Ver Clases de complejidad P y NP y Valor absoluto
Wiki
El término wiki (palabra que proviene del hawaiano wiki, 'rápido') alude al nombre que recibe una comunidad virtual, cuyas páginas son editadas directamente desde el navegador, donde los mismos usuarios crean, modifican, corrigen o eliminan contenidos que, habitualmente, son compartidos por cualquier otro usuario.
Ver Clases de complejidad P y NP y Wiki
Ver también
Conjeturas matemáticas
- Agujero de gusano
- Clases de complejidad P y NP
- Conjetura
- Conjetura abc
- Conjetura de Aanderaa-Karp-Rosenberg
- Conjetura de Beal
- Conjetura de Birch y Swinnerton-Dyer
- Conjetura de Carathéodory
- Conjetura de Catalan
- Conjetura de Coase
- Conjetura de Collatz
- Conjetura de Fermat–Catalan
- Conjetura de Hall
- Conjetura de Hirsch
- Conjetura de Hodge
- Conjetura de Ramanujan–Petersson
- Conjetura de Schanuel
- Conjetura de gravedad débil
- Conjetura de protección de la cronología
- Conjetura del Juego Único
- Conjetura del corredor solitario
- Conjetura jacobiana
- Conjeturas de Weil
- Duodécimo problema de Hilbert
- Forma espacial
- Hipótesis de Lindelöf
- Hipótesis de Riemann
- Hipótesis generalizada de Riemann
- Número de Sierpiński
- Principio de autoconsistencia de Nóvikov
- Problema de sin tres en línea
- Programa de Langlands
- Simetría especular homológica
- Teorema de De Branges
Informática de 1956
- Clases de complejidad P y NP
- Conferencia de Dartmouth
- Gramática libre de contexto
- Jerarquía de Chomsky
Introducciones relacionadas a la ciencia de la computación de 1956
- Bendix G-15
- Clases de complejidad P y NP
- GM-NAA I/O
- IBM 305 RAMAC
- Laboratorio Shockley de Semiconductores
- Memoria programable de solo lectura
Optimización
- Clases de complejidad P y NP
- Condiciones de Karush-Kuhn-Tucker
- Control óptimo
- Descenso del gradiente
- Eficiencia bayesiana
- Eficiencia de Pareto
- Extremos de una función
- Mathematical Optimization Society
- Mediana geométrica
- Metodología de superficie de respuesta
- Multiplicadores de Lagrange
- Número del pastel
- NP-completo
- Optimización (matemática)
- Optimización con restricciones
- Optimización de hiperparámetros
- Optimización hidrológica
- Optimización multiobjetivo
- Región factible
- Restricción (matemáticas)
- Solución de esquina
- Tanteo walrasiano
- Teorema del cortador perezoso
Problemas del milenio
- Clases de complejidad P y NP
- Conjetura de Birch y Swinnerton-Dyer
- Conjetura de Hodge
- Hipótesis de Poincaré
- Hipótesis de Riemann
- Problemas del milenio
Problemas matemáticos no resueltos
- Clases de complejidad P y NP
- Cuadrado mágico
- Cuadruplete primo
- Función suma de divisores
- Hipótesis generalizada de Riemann
- Número cuasiperfecto
- Número de Lucas
- Número de Pell
- Número primo de Newman-Shanks-Williams
- Número primo palindrómico
- Número primo primo
- Poliedro de Szilassi
- Problema de Galois inverso
- Problema de Thomson
- Problema del círculo de Gauss
- Problemas de Hilbert
- Problemas de Smale
- Problemas del milenio
Problemas no resueltos de las ciencias de la computación
- Clases de complejidad P y NP
- Conjetura de Aanderaa-Karp-Rosenberg
- Conjetura de Černý
- Conjetura del Juego Único
- Factorización de enteros
- Función unidireccional
- Logaritmo discreto
- Problema de separación de palabras
- Problema del isomorfismo de grafos
- Problema k-server
También se conoce como P = NP, P versus NP, P vs NP, P-NP, P=NP, Problema P - NP, Problema P = NP, Problema P-NP, Problema P=NP, Problema ¿P=NP?.