¡Más rápido que el navegador!
114 relaciones: Algoritmo cuántico, Algoritmo de aproximación, Algoritmo de Bowyer-Watson, Algoritmo de Dijkstra, Algoritmo de Dinic, Algoritmo de Floyd-Warshall, Algoritmo de Shor, Algoritmo de triangulación voraz, Algoritmo de Ukkonen, Algoritmo LLL, Alineamiento estructural, Alineamiento múltiple de secuencias, Alistair Sinclair, Autómata finito, BQP, Circuitos booleanos, Clase de complejidad, Clases de complejidad P y NP, Co-NP-completo, Codificación Huffman, Complejidad temporal, Complejidad y criptografía, Computación cuántica óptica, Conjunto independiente, Corrección de errores hacia adelante, Criptoanálisis, DTIME, Equilibrio estructural, EXPSPACE, EXPTIME, Factor primo, Factorización de enteros, Fórmula de los números primos, FNP (clase de complejidad), Forma normal conjuntiva, FP (clase de complejidad), Función booleana 2-monótona, Función booleana regular, Función umbral, Función unidireccional, Gabriel Lamé, Generador de números pseudoaleatorios criptográficamente seguro, Geografía generalizada, Grafo de Ramanujan, Grafo multipartito, Grafo perfecto, Grafos observables, Gramática de concatenación de rango, Gramática formal, Gramática indexada, ..., Hipergrafo crítico, Hipergrafo minimal, Juego de mayoría ponderada, Leonid Jachián, Leslie Valiant, Libreta de un solo uso, Logaritmo discreto, Máquina de Turing, Michael Oser Rabin, Número primo, NC (clase de complejidad), NP (clase de complejidad), NP-completo, NP-hard, Numeral-P-completo, P (desambiguación), P/poly, PH (clase de complejidad), Polinomio, PolyL, Premio Fulkerson, Premio Gödel, Problema de isomorfismo de subgrafos, Problema de la cobertura de cliques, Problema de la cobertura de vértices, Problema de la división de un conjunto, Problema de la medida de Klee, Problema de satisfacción de restricciones, Problema de Simon, Problema del árbol de Steiner, Problema del isomorfismo de grafos, Problemas de Smale, Programación lineal, PSPACE, QMA (Clase de complejidad), QMA (Complejidad), Quickhull, Reducción (complejidad), Richard Karp, Rotación de árboles, RSA, SC (clase de complejidad), Soft computing, Stephen Cook, Teoría Cuántica de la Complejidad Computacional, Teoría de grafos, Teoría de la complejidad computacional, Teoría de la información cuántica, Teorema de BEST, Teorema de Cook, Teorema de Kirchhoff, Teorema de la jerarquía temporal, Teorema de Toda, Tesis de Church-Turing, Tesis de Cobham, Test de Pépin, Test de primalidad, Test de primalidad AKS, TFNP, Tiempo de ejecución, Tiempo polinómico incremental, Tiempo pseudopolinómico, Transformación polinómica, UP (clase de complejidad). Expandir índice (64 más) »
Algoritmo cuántico
Un algoritmo cuántico es un algoritmo que se ejecuta en un modelo realista de computación cuántica, como el modelo de circuito cuántico, como el que se ilustra en la figura.
¡Nuevo!!: P (clase de complejidad) y Algoritmo cuántico · Ver más »
Algoritmo de aproximación
En ciencias de la computación e investigación de operaciones, un algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización.
¡Nuevo!!: P (clase de complejidad) y Algoritmo de aproximación · Ver más »
Algoritmo de Bowyer-Watson
En geometría computacional, el Algoritmo de Bowyer–Watson es un método para calcular la triangulación de Delaunay de un conjunto finito de puntos en cualquier número de dimensiones. El algoritmo se puede emplear también para construir el Diagrama de Voronoi de los puntos, el cual es el grafo dual de dicha triangulación.
¡Nuevo!!: P (clase de complejidad) y Algoritmo de Bowyer-Watson · 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!!: P (clase de complejidad) y Algoritmo de Dijkstra · Ver más »
Algoritmo de Dinic
El algoritmo de Dinic es un algoritmo de Tiempo polinómico para la computación de un Flujo maximal en una red de flujo, concebida en 1970 por el científico de la computación Yefim Dinitz, israelí de origen soviético.
¡Nuevo!!: P (clase de complejidad) y Algoritmo de Dinic · Ver más »
Algoritmo de Floyd-Warshall
En informática, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados.
¡Nuevo!!: P (clase de complejidad) y Algoritmo de Floyd-Warshall · Ver más »
Algoritmo de Shor
En computación cuántica, el algoritmo de Shor es un algoritmo cuántico para descomponer en factores un número N en tiempo O((log N)3) y espacio O(logN), así nombrado por Peter Shor.
¡Nuevo!!: P (clase de complejidad) y Algoritmo de Shor · Ver más »
Algoritmo de triangulación voraz
El Algoritmo de Triangulación Voraz es un método para calcular una triangulación de un polígono o de una nube de puntos mediante un método voraz, que consiste en añadir aristas a la solución de una en una uniendo el par de vértices más próximos entre sí, con la condición de que una nueva arista no puede cortar a otra previamente añadida al resultado.
¡Nuevo!!: P (clase de complejidad) y Algoritmo de triangulación voraz · Ver más »
Algoritmo de Ukkonen
En ciencias de la computación, el algoritmo de Ukkonen es un algoritmo on-line, con tiempo de computación lineal, para construir un árbol de sufijos de una cadena S. Este algoritmo fue propuesto por Esko Ukkonen en 1995.
¡Nuevo!!: P (clase de complejidad) y Algoritmo de Ukkonen · Ver más »
Algoritmo LLL
El algoritmo de simplificación de bases de retículos de Lenstra–Lenstra–Lovász (LLL) es un algoritmo de simplificación de retículos de complejidad polinomial inventado por Arjen Lenstra, Hendrik Lenstra y László Lovász en 1982.
¡Nuevo!!: P (clase de complejidad) y Algoritmo LLL · Ver más »
Alineamiento estructural
Un alineamiento estructural es un tipo de alineamiento de secuencias basado en la comparación de la forma.
¡Nuevo!!: P (clase de complejidad) y Alineamiento estructural · Ver más »
Alineamiento múltiple de secuencias
Un alineamiento múltiple de secuencias (Multiple sequence alignment MSA, por sus siglas en inglés) es un alineamiento de tres o más secuencias biológicas, generalmente proteínas, ADN o ARN.
¡Nuevo!!: P (clase de complejidad) y Alineamiento múltiple de secuencias · Ver más »
Alistair Sinclair
Alistair Sinclair es un informático teórico británico.
¡Nuevo!!: P (clase de complejidad) y Alistair Sinclair · Ver más »
Autómata finito
Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.
¡Nuevo!!: P (clase de complejidad) y Autómata finito · Ver más »
BQP
En teoría de la complejidad computacional, BQP (tiempo polinomial cuántico con error acotado) es la clase de problemas de decisión decidibles por un ordenador cuántico en tiempo polinomial con una probabilidad de error de como mucho 1/3 para todas las instancias.
¡Nuevo!!: P (clase de complejidad) y BQP · Ver más »
Circuitos booleanos
En la teoría de la complejidad computacional y complejidad de circuitos, un circuito booleano es un modelo matemático para circuitos lógicos digitales combinacionales.
¡Nuevo!!: P (clase de complejidad) y Circuitos booleanos · 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!!: P (clase de complejidad) y Clase de complejidad · 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!!: P (clase de complejidad) y Clases de complejidad P y NP · Ver más »
Co-NP-completo
En teoría de la complejidad computacional, la clase de complejidad co-NP-completo es el conjunto de los problemas de decisión más difíciles de la clase co-NP, en el sentido de que son los que menos parecen pertenecer a la clase de complejidad P. De encontrarse una forma de resolver un problema en co-NP-completo en tiempo polinómico, el algoritmo utilizado serviría para resolver todos los problemas de co-NP con la misma complejidad.
¡Nuevo!!: P (clase de complejidad) y Co-NP-completo · Ver más »
Codificación Huffman
En ciencias de la computación y teoría de la información, la codificación Huffman es un algoritmo usado para compresión de datos.
¡Nuevo!!: P (clase de complejidad) y Codificación Huffman · Ver más »
Complejidad temporal
En informática, la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo que lleva ejecutar un algoritmo.
¡Nuevo!!: P (clase de complejidad) y Complejidad temporal · Ver más »
Complejidad y criptografía
La criptografía es la ciencia encargada del estudio y diseño de sistemas que permiten ocultar información.
¡Nuevo!!: P (clase de complejidad) y Complejidad y criptografía · Ver más »
Computación cuántica óptica
La computación cuántica óptica es una propuesta experimental y teórica que pretende servir como base para el desarrollo de la computación cuántica.
¡Nuevo!!: P (clase de complejidad) y Computación cuántica óptica · Ver más »
Conjunto independiente
En teoría de grafos, un conjunto independiente o estable es un conjunto de vértices en un grafo tal que ninguno de sus vértices es adyacente a otro.
¡Nuevo!!: P (clase de complejidad) y Conjunto independiente · Ver más »
Corrección de errores hacia adelante
En telecomunicaciones, teoría de la información y teoría de la codificación, la corrección de errores hacia adelante (en inglés, forward error correction o FEC) o codificación de canal es una técnica utilizada para controlar los errores en la transmisión de datos a través de canales de comunicación poco fiables o ruidosos.
¡Nuevo!!: P (clase de complejidad) y Corrección de errores hacia adelante · Ver más »
Criptoanálisis
El criptoanálisis (del griego kryptós, 'escondido' y analýein, 'desatar') es la parte de la criptología que se dedica al estudio de sistemas criptográficos con el fin de encontrar debilidades en los sistemas y romper su seguridad sin el conocimiento de información secreta.
¡Nuevo!!: P (clase de complejidad) y Criptoanálisis · Ver más »
DTIME
En teoría de la complejidad computacional, la clase de complejidad DTIME(f(n)) (también llamada TIME(f(n))) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(f(n)), y espacio ilimitado.
¡Nuevo!!: P (clase de complejidad) y DTIME · Ver más »
Equilibrio estructural
En análisis de redes sociales, el equilibrio estructural es una propiedad deseable de una red social, usualmente representada como grafo signado, en que los actores o nodos de una red social se agrupan y relacionan consistentemente de acuerdo a sus cogniciones o percepciones.
¡Nuevo!!: P (clase de complejidad) y Equilibrio estructural · Ver más »
EXPSPACE
En teoría de la complejidad computacional, la clase de complejidad EXPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2p(n)), donde p(n) es una función polinomial sobre n. De acuerdo con el Teorema de Savitch, esta clase es igual a la que considera máquinas de Turing no deterministas.
¡Nuevo!!: P (clase de complejidad) y EXPSPACE · 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!!: P (clase de complejidad) y EXPTIME · Ver más »
Factor primo
En teoría de números, los factores primos de un número entero son los números primos divisores exactos de ese número entero.
¡Nuevo!!: P (clase de complejidad) y Factor primo · Ver más »
Factorización de enteros
En teoría de números, la factorización de enteros, factorización de primos, factorización en primos o árbol de factorización consiste en descomponer un número compuesto (no primo) en divisores no triviales, que cuando se multiplican dan el número original.
¡Nuevo!!: P (clase de complejidad) y Factorización de enteros · Ver más »
Fórmula de los números primos
En matemáticas, una fórmula de los números primos es aquella que genera los números primos, exactamente y sin excepción alguna.
¡Nuevo!!: P (clase de complejidad) y Fórmula de los números primos · 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!!: P (clase de complejidad) y FNP (clase de complejidad) · 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!!: P (clase de complejidad) y Forma normal conjuntiva · 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!!: P (clase de complejidad) y FP (clase de complejidad) · Ver más »
Función booleana 2-monótona
En matemáticas, una función booleana 2-monótona (más conocida en inglés como 2-monotone boolean function) es una función booleana monótona ƒ: n →, para la cual existe un ordenamiento lineal de sus variables w1, w2,..., wn, de modo que se convierte también en una función booleana regular.
¡Nuevo!!: P (clase de complejidad) y Función booleana 2-monótona · Ver más »
Función booleana regular
En matemáticas, una función booleana regular es una clase particular de funciones booleanas que toma en cuenta el ordenamiento de sus distintos parámetros.
¡Nuevo!!: P (clase de complejidad) y Función booleana regular · Ver más »
Función umbral
En matemáticas, una función umbral (más conocida en inglés como threshold function) es una función booleana monótona ƒ: n →, donde existen n+1 reales no negativos w1, w2,..., wn, t tales que:.
¡Nuevo!!: P (clase de complejidad) y Función umbral · Ver más »
Función unidireccional
Las funciones unidireccionales también conocidas como funciones de un solo sentido son funciones que tienen la propiedad de ser fáciles de calcular pero difíciles de invertir.
¡Nuevo!!: P (clase de complejidad) y Función unidireccional · Ver más »
Gabriel Lamé
Père de Gabriel Léon Jean Baptiste Lamé (22 de julio de 1795 - 1 de mayo de 1870) fue un matemático francés.
¡Nuevo!!: P (clase de complejidad) y Gabriel Lamé · Ver más »
Generador de números pseudoaleatorios criptográficamente seguro
Un generador de números pseudoaleatorios criptográficamente seguro (CSPRNG, del inglés «Cryptographically Secure PseudoRandom Number Generator») es un Generador de números pseudoaleatorios (PRNG) con características que lo hacen adecuado para su uso en criptografía.
¡Nuevo!!: P (clase de complejidad) y Generador de números pseudoaleatorios criptográficamente seguro · Ver más »
Geografía generalizada
En teoría de la complejidad computacional, el juego de geografía generalizada es un conocido problema de PSPACE completo.
¡Nuevo!!: P (clase de complejidad) y Geografía generalizada · Ver más »
Grafo de Ramanujan
En la teoría de grafos espectrales, un grafo de Ramanujan, es un grafo regular cuya brecha espectral es casi tan grande como sea posible (véase la teoría de grafos extremales).
¡Nuevo!!: P (clase de complejidad) y Grafo de Ramanujan · Ver más »
Grafo multipartito
En teoría de grafos, un grafo k-partito es un grafo cuyos vértices están o pueden ser particionados en k diferentes conjuntos independientes.
¡Nuevo!!: P (clase de complejidad) y Grafo multipartito · Ver más »
Grafo perfecto
En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo.
¡Nuevo!!: P (clase de complejidad) y Grafo perfecto · Ver más »
Grafos observables
La idea de un grafo observable es un grafo dirigido y coloreado donde un agente se desplaza de vértice en vértice sobre las aristas (respetando la dirección de las aristas) y que solo es capaz de almacenar la secuencia de los colores de las aristas (o los vértices) en orden, pero a pesar de ello, luego de una cantidad T finita de aristas (o vértices) el agente sabe exactamente el vértice en el que está.
¡Nuevo!!: P (clase de complejidad) y Grafos observables · Ver más »
Gramática de concatenación de rango
Gramática de concatenación de rango (GCR) es una gramática formal desarrollada por Pierre Boullier en 1998 como un intento de caracterizar una serie de fenómenos del lenguaje natural, tales como los números chinos y el orden aleatorio de palabras alemanas, los cuales están fuera de los límites de los formalismos gramáticos sensibles al contexto.
¡Nuevo!!: P (clase de complejidad) y Gramática de concatenación de rango · Ver más »
Gramática formal
Una gramática formal es una estructura lógico-matemática con un conjunto de reglas de formación que definen las cadenas de caracteres admisibles en un determinado lenguaje formal o lengua natural.
¡Nuevo!!: P (clase de complejidad) y Gramática formal · Ver más »
Gramática indexada
Las gramáticas indexadas son una generalización de gramáticas libres de contexto en que los símbolos no terminales están equipados con listas de banderas o símbolos de índice.
¡Nuevo!!: P (clase de complejidad) y Gramática indexada · Ver más »
Hipergrafo crítico
En teoría de hipergrafos, el hipergrafo crítico o simplemente el crítico de un hipergrafo H definido sobre un conjunto base A, es el hipergrafo σ(H) conformado por los subconjuntos de A tal que cada uno de sus elementos intersecan a una hiperarista de H diferente.
¡Nuevo!!: P (clase de complejidad) e Hipergrafo crítico · Ver más »
Hipergrafo minimal
En teoría de hipergrafos, el hipergrafo minimal o simplemente minimal de un hipergrafo H definido sobre un conjunto base A, es el hipergrafo μ(H) conformado por todas las hiperaristas mínimas de H, es decir, aquellas tal que ninguna otra es subconjunto de ellas.
¡Nuevo!!: P (clase de complejidad) e Hipergrafo minimal · Ver más »
Juego de mayoría ponderada
En teoría de juegos, más específicamente en teoría de juegos cooperativos, un juego con pesos o juego de mayoría ponderada (más comúnmente conocido en inglés como weighted game) es un tipo de juego simple en que los votos de algunos jugadores pueden valer más que los de otros.
¡Nuevo!!: P (clase de complejidad) y Juego de mayoría ponderada · Ver más »
Leonid Jachián
Leonid Guénrijovich Jachián (armenio: Լեոնիդ Գենրիխովիչ Խաչիյան; ruso: Леонид Генрихович Хачиян; San Petersburgo, Rusia, 3 de mayo de 1952 - Nueva Jersey, Estados Unidos, 29 de abril de 2005) fue un connotado matemático ruso de origen armenio, catedrático de ciencias de la computación de la Universidad Rutgers, principalmente conocido por su demostración de la polinomialidad de la programación lineal.
¡Nuevo!!: P (clase de complejidad) y Leonid Jachián · Ver más »
Leslie Valiant
Leslie Gabriel Valiant (nacido el 28 de marzo de 1949) es un informático teórico británico.
¡Nuevo!!: P (clase de complejidad) y Leslie Valiant · Ver más »
Libreta de un solo uso
En criptografía, la libreta de uso único, también llamado libreta de un solo uso (del inglés one-time pad), es un tipo de algoritmos de cifrado por el que el texto en claro se combina con una clave aleatoria o «libreta» igual de larga que el texto en claro y que sólo se utiliza una vez.
¡Nuevo!!: P (clase de complejidad) y Libreta de un solo uso · Ver más »
Logaritmo discreto
En álgebra abstracta, se conoce como logaritmo discreto de y en base g, donde g e y son elementos de un grupo cíclico finito G, a la solución x de la ecuación gx.
¡Nuevo!!: P (clase de complejidad) y Logaritmo discreto · 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!!: P (clase de complejidad) y Máquina de Turing · Ver más »
Michael Oser Rabin
Michael Oser Rabin (nacido en 1931 en Breslavia, Alemania, hoy en día parte de Polonia) es un notable científico de la computación y ganador del Premio Turing, el galardón más prestigioso en el campo.
¡Nuevo!!: P (clase de complejidad) y Michael Oser Rabin · Ver más »
Número primo
En matemáticas, un número primo es un número natural mayor que 1 que tiene únicamente dos divisores positivos distintos: él mismo y el 1.
¡Nuevo!!: P (clase de complejidad) y Número primo · Ver más »
NC (clase de complejidad)
En teoría de la complejidad computacional, la clase de complejidad NC (la clase de Nick) es el conjunto de los problemas de decisión que pueden ser resueltos mediante computación paralela con un número polinómico de procesadores en tiempo polilogarítmico.
¡Nuevo!!: P (clase de complejidad) y NC (clase de complejidad) · 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!!: P (clase de complejidad) 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!!: P (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!!: P (clase de complejidad) y NP-hard · Ver más »
Numeral-P-completo
En teoría de la complejidad computacional, la clase de complejidad #P-completo (se pronuncia numeral-P-completo) es el conjunto de los problemas de conteo que pertenecen a #P tales que todo problema de #P se puede reducir en todos los de $P-completo en tiempo polinómico.
¡Nuevo!!: P (clase de complejidad) y Numeral-P-completo · Ver más »
P (desambiguación)
P (o p) puede designar.
¡Nuevo!!: P (clase de complejidad) y P (desambiguación) · Ver más »
P/poly
En la teoría de la complejidad computacional, P/poly es la clase de complejidad de los lenguajes reconocidos por una máquina de Turing de tiempo polinomial con una función de asesoramiento limitada polinomialmente.
¡Nuevo!!: P (clase de complejidad) y P/poly · Ver más »
PH (clase de complejidad)
En teoría de la complejidad computacional, la clase de complejidad PH es la unión de todas las clases de complejidad de la jerarquía polinómica.
¡Nuevo!!: P (clase de complejidad) y PH (clase de complejidad) · Ver más »
Polinomio
En matemáticas, polinomio (del latín: polynomium, y este del griego: πολυς, polys, ‘muchos’ y νόμος, nómos, ‘regla’, ‘prescripción’, ‘distribución’) es una expresión algebraica formada por la suma de varios monomios o términos, cada uno de los cuales es el producto de.
¡Nuevo!!: P (clase de complejidad) y Polinomio · Ver más »
PolyL
En complejidad computacional, PolyL es una clase de complejidad que contiene aquellos lenguajes para los cuales existe un algoritmo determinista cuyo espacio de decisión requerido está acotado por un polilogaritmo en función del tamaño de la entrada.
¡Nuevo!!: P (clase de complejidad) y PolyL · Ver más »
Premio Fulkerson
El Premio Fulkerson es un premio otorgado por la Mathematical Optimization Society (MOS) y la American Mathematical Society (AMS) a autores de artículos científicos destacados en el área de las matemáticas discretas.
¡Nuevo!!: P (clase de complejidad) y Premio Fulkerson · Ver más »
Premio Gödel
El Premio Gödel es un premio que se entrega a autores de artículos relacionados con teoría de la computación.
¡Nuevo!!: P (clase de complejidad) y Premio Gödel · Ver más »
Problema de isomorfismo de subgrafos
En complejidad computacional, el Problema de isomorfismo de subgrafos, también a veces llamado Problema de matching de subgrafos, es un problema de decisión NP-completo, que formalmente, se define de la siguiente manera: La NP-completitud del problema se demuestra mediante la reducción de este problema al Problema de la clique.
¡Nuevo!!: P (clase de complejidad) y Problema de isomorfismo de subgrafos · Ver más »
Problema de la cobertura de cliques
En teoría de la complejidad computacional, el problema de la cobertura de cliques es un problema de decisión NP-completo de la teoría de grafos.
¡Nuevo!!: P (clase de complejidad) y Problema de la cobertura de cliques · Ver más »
Problema de la cobertura de vértices
En ciencias de la computación, el Problema de la cobertura de vértices es un problema NP-completo, que pertenece a los 21 problemas NP-completos de Karp.
¡Nuevo!!: P (clase de complejidad) y Problema de la cobertura de vértices · Ver más »
Problema de la división de un conjunto
En complejidad computacional, el problema de división de un conjunto (más comúnmente conocido en inglés como Set splitting problem) es el siguiente problema de decisión: dada una familia F de subconjuntos de un conjunto finito S, ¿existe una partición de S en dos subconjuntos S1 y S2 tales que ninguno de los elementos de F esté completamente en S1 o S2? Este problema es NP-completo.
¡Nuevo!!: P (clase de complejidad) y Problema de la división de un conjunto · Ver más »
Problema de la medida de Klee
En la geometría computacional, el problema de la medida de Klee es el problema de determinar cuan eficientemente la medida de una unión (multidimensional) de rangos rectangulares puede ser calculada.
¡Nuevo!!: P (clase de complejidad) y Problema de la medida de Klee · Ver más »
Problema de satisfacción de restricciones
Problemas de satisfacción de restricciones (CSP, por sus siglas en inglés), son problemas matemáticos definidos como un conjunto de objetos tal que su estado debe satisfacer un número de restricciones o limitaciones.
¡Nuevo!!: P (clase de complejidad) y Problema de satisfacción de restricciones · Ver más »
Problema de Simon
En álgebra abstracta y computación cuántica, el problema planteado por Daniel R. Simon (conocido como problema de Simon) es un caso particular del problema del subgrupo oculto (Hidden Subgroup Problem, HSP), el cual ha sido útil para el planteamiento de algoritmos cuánticos que son eficientes, a diferencia de sus homólogos clásicos, permitiendo resolver problemas teóricos propuestos en las últimas décadas cuyas soluciones son de vital importancia en el campo de la computación cuántica.
¡Nuevo!!: P (clase de complejidad) y Problema de Simon · Ver más »
Problema del árbol de Steiner
El problema del árbol de Steiner, nombrado en honor a Jakob Steiner, es un problema de optimización combinatoria consistente en buscar la interconexión más corta para un conjunto de elementos dado.
¡Nuevo!!: P (clase de complejidad) y Problema del árbol de Steiner · Ver más »
Problema del isomorfismo de grafos
El problema del isomorfismo gráfico es el problema computacional para determinar si dos gráficos finitos son isomórficos. No se sabe que el problema se pueda resolver en tiempo polinomial ni que sea NP-completo y, por lo tanto, puede estar en la clase de complejidad computacional NP-intermedia.
¡Nuevo!!: P (clase de complejidad) y Problema del isomorfismo de grafos · Ver más »
Problemas de Smale
Los llamados problemas de Smale son una lista de 18 problemas matemáticos no resueltos propuesta por Steve Smale en 2000.
¡Nuevo!!: P (clase de complejidad) y Problemas de Smale · Ver más »
Programación lineal
La programación lineal (LP, también conocida como optimización lineal) es el campo de la programación matemática dedicado a maximizar o minimizar (optimizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones expresadas mediante un sistema de ecuaciones o inecuaciones también lineales.
¡Nuevo!!: P (clase de complejidad) y Programación lineal · 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!!: P (clase de complejidad) y PSPACE · Ver más »
QMA (Clase de complejidad)
En teoría de la complejidad, la clase de complejidad QMA (Quantum Merlin Authur) es el conjunto de los problemas de decisión o lenguajes que una respuesta SI puede llegar a verificarse por una prueba cuántica interactiva de un solo mensaje en un tiempo polinómico (estado cuántico) ejecutado en una computadora cuántica.
¡Nuevo!!: P (clase de complejidad) y QMA (Clase de complejidad) · Ver más »
QMA (Complejidad)
En teoría de la complejidad, la clase de complejidad QMA (Quantum Merlin Authur) es el conjunto de los problemas de decisión o lenguajes que una respuesta SI puede llegar a verificarse por una prueba cuántica interactiva de un solo mensaje en un tiempo polinómico (estado cuántico) ejecutado en una computadora cuántica.
¡Nuevo!!: P (clase de complejidad) y QMA (Complejidad) · Ver más »
Quickhull
Quickhull es un método para calcular el cierre convexo de un conjunto finito de puntos (generalmente en el plano 2D, pero también existen versiones para dimensiones superiores).
¡Nuevo!!: P (clase de complejidad) y Quickhull · Ver más »
Reducción (complejidad)
En teoría de la computación y teoría de la complejidad computacional, una reducción es una transformación de un problema a otro problema.
¡Nuevo!!: P (clase de complejidad) y Reducción (complejidad) · Ver más »
Richard Karp
Richard Manning Karp (Boston, (Estados Unidos), 3 de enero de 1935) es un científico de la computación, conocido por su investigación en teoría de algoritmos, por lo que recibió el Premio Turing en 1985, el premio del Instituto Franklin en 2004 y el Premio Kioto en 2008.
¡Nuevo!!: P (clase de complejidad) y Richard Karp · Ver más »
Rotación de árboles
En matemáticas discretas, Rotación de árboles es una operación en un árbol binario que cambia la estructura sin interferir con el orden de los elementos.
¡Nuevo!!: P (clase de complejidad) y Rotación de árboles · Ver más »
RSA
En criptografía, RSA (Rivest, Shamir y Adleman) es un sistema criptográfico de clave pública desarrollado en 1979, que utiliza factorización de números enteros.
¡Nuevo!!: P (clase de complejidad) y RSA · Ver más »
SC (clase de complejidad)
En complejidad computacional, SC (Steve's Class, en español Clase de Steve en honor a Stephen Cook) es una clase de complejidad que incluye a los problemas resolubles por una máquina de Turing determinista en tiempo polinomial (clase P) y espacio polilogarítmico (clase PolyL) (esto es un espacio de orden O(logk n) para alguna constante k).
¡Nuevo!!: P (clase de complejidad) y SC (clase de complejidad) · Ver más »
Soft computing
Soft computing es una rama de la Inteligencia Artificial que engloba diversas técnicas empleadas para solucionar problemas que manejan información incompleta, con incertidumbre y/o inexacta.
¡Nuevo!!: P (clase de complejidad) y Soft computing · Ver más »
Stephen Cook
Stephen Arthur Cook (1939, Búfalo (Nueva York)) es un reconocido científico de la computación.
¡Nuevo!!: P (clase de complejidad) y Stephen Cook · Ver más »
Teoría Cuántica de la Complejidad Computacional
La teoría cuántica de la complejidad computacional es un subcampo de la teoría de la complejidad computacional que estudia las diferentes clases de complejidad que existen desde la perspectiva de la computación cuántica.
¡Nuevo!!: P (clase de complejidad) y Teoría Cuántica de la Complejidad Computacional · 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!!: P (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!!: P (clase de complejidad) y Teoría de la complejidad computacional · Ver más »
Teoría de la información cuántica
La teoría de la información cuántica es una disciplina que incorpora técnicas de las matemáticas, la física y las ciencias de la computación y que se ocupa, por un lado, de describir qué es exactamente la información cuántica (y que la diferencia de la clásica) y por otro, de su transmisión.
¡Nuevo!!: P (clase de complejidad) y Teoría de la información cuántica · Ver más »
Teorema de BEST
En teoría de grafos, el teorema de BEST provee una fórmula producto para el número de ciclos eulerianos en un grafo (orientado) dirigido.
¡Nuevo!!: P (clase de complejidad) y Teorema de BEST · 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!!: P (clase de complejidad) y Teorema de Cook · Ver más »
Teorema de Kirchhoff
En el campo matemático de la teoría de grafos, el teorema de Kirchhoff, nombrado por Gustav Kirchhoff es un teorema sobre el número de árboles de expansión en un grafo, mostrando que ese número puede ser computado en tiempo polinomial como el determinante de una matriz derivada del grafo.
¡Nuevo!!: P (clase de complejidad) y Teorema de Kirchhoff · Ver más »
Teorema de la jerarquía temporal
En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing.
¡Nuevo!!: P (clase de complejidad) y Teorema de la jerarquía temporal · Ver más »
Teorema de Toda
El teorema de Toda es un teorema demostrado por Seinosuke Toda en el artículo de 1991 "PP is as Hard as the Polynomial-Time Hierarchy", que le dio a su autor el Premio Gödel en 1998.
¡Nuevo!!: P (clase de complejidad) y Teorema de Toda · Ver más »
Tesis de Church-Turing
En teoría de la computabilidad, la tesis de Church-Turing formula hipotéticamente la equivalencia entre los conceptos de función computable y máquina de Turing, que expresado en lenguaje corriente vendría a ser "todo algoritmo es equivalente a una máquina de Turing".
¡Nuevo!!: P (clase de complejidad) y Tesis de Church-Turing · Ver más »
Tesis de Cobham
En ciencias de la computación, la tesis de Cobham, también conocida como la tesis de Cobham-Edmonds (llamada así por Alan Cobham y Jack Edmonds) afirma que los problemas tratables o "fácilmente computables" son los problemas computables en tiempo polinómico.
¡Nuevo!!: P (clase de complejidad) y Tesis de Cobham · Ver más »
Test de Pépin
En matemáticas, el test de Pépin (por el matemático francés P. Pépin) es un test de primalidad que se puede emplear para determinar si un número de Fermat es primo.
¡Nuevo!!: P (clase de complejidad) y Test de Pépin · 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!!: P (clase de complejidad) y Test de primalidad · Ver más »
Test de primalidad AKS
El test de primalidad AKS o algoritmo AKS es un algoritmo determinista que decide en tiempo polinómico si un número natural es primo o compuesto.
¡Nuevo!!: P (clase de complejidad) y Test de primalidad AKS · Ver más »
TFNP
En complejidad computacional, TFNP (en inglés: "total function nondeterministic polynomial") es una clase de complejidad que es subclase de FNP, donde la existencia de una solución está garantizada.
¡Nuevo!!: P (clase de complejidad) y TFNP · Ver más »
Tiempo de ejecución
Se denomina tiempo de ejecución (runtime en inglés) al intervalo de tiempo en el que un programa de computadora se ejecuta en un sistema operativo.
¡Nuevo!!: P (clase de complejidad) y Tiempo de ejecución · Ver más »
Tiempo polinómico incremental
En complejidad computacional, el tiempo polinómica incremental (en inglés, incremental polynomial time) se refiere a cuando el tiempo de ejecución de un algoritmo de enumeración de un conjunto es polinomial en términos de la entrada y de los elementos de la salida hasta ahora computados.
¡Nuevo!!: P (clase de complejidad) y Tiempo polinómico incremental · Ver más »
Tiempo pseudopolinómico
En teoría de la complejidad computacional, un algoritmo numérico se ejecuta en tiempo pseudopolinómico o tiempo seudopolinómico si su tiempo de ejecución es polinómico en el valor numérico de la entrada, pudiendo ser este valor exponencial en el largo de la entrada, es decir, en el número de dígitos que la conforman.
¡Nuevo!!: P (clase de complejidad) y Tiempo pseudopolinómico · Ver más »
Transformación polinómica
En complejidad computacional, una transformación polinómica, reducción polinómica o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza inmediatamente, y a través de un tiempo polinómico, la existencia de un algoritmo que resuelve el segundo.
¡Nuevo!!: P (clase de complejidad) y Transformación polinómica · Ver más »
UP (clase de complejidad)
En teoría de la complejidad computacional, la clase de complejidad UP (tiempo polinómico, no determinista, no ambiguo) es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista tal que la solución si existe es única.
¡Nuevo!!: P (clase de complejidad) y UP (clase de complejidad) · Ver más »
Redirecciona aquí:
Clase P, P (Complejidad computacional), PTIME, Polinomialidad, Tiempo de ejecucion polinomico, Tiempo de ejecucion polinómico, Tiempo de ejecución polinómico, Tiempo polinomial, Tiempo polinomico, Tiempo polinómico.
