¡Más rápido que el navegador!
41 relaciones: Alexander Razborov, Algoritmo de aproximación, Algoritmo galáctico, Charlie Eppes, Ciencias de la computación, Circuitos booleanos, Complejidad temporal, Complejidad y criptografía, Conjetura, Dimensión bipartita, Esquema de aproximación de tiempo polinómico, FNP (clase de complejidad), FP (clase de complejidad), Función unidireccional, Mario de Jesús Pérez Jiménez, Matemática discreta, Número primo fuerte, Nonograma, NP (clase de complejidad), NP-completo, NP-hard, P (clase de complejidad), Permanente (matemáticas), Problema de satisfacción de restricciones, Problema del camino más corto, Problema del camino más largo, Problema del conjunto de cobertura, Problema del isomorfismo de grafos, Problema del viajante, Problemas de Smale, Programación Semidefinida, Protocolo de Ko-Lee-Cheon-Hang-Park, Red de ordenamiento, Richard Lipton, Robert M. Solovay, Teoría de la complejidad computacional, Teoría de la computación, Teorema de la jerarquía temporal, Tiempo pseudopolinómico, Totalmente NP-completo, Veintiún problemas NP-completos de Karp.
Alexander Razborov
Aleksandr Aleksandrovich Razborov (Алекса́ндр Алекса́ндрович Разбо́ров; nacido el 16 de febrero de 1963), a veces conocido como Sasha Razborov, es un matemático soviético y y teórico computacional.
¡Nuevo!!: Clases de complejidad P y NP y Alexander Razborov · 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!!: Clases de complejidad P y NP y Algoritmo de aproximación · Ver más »
Algoritmo galáctico
Un algoritmo galáctico es aquel que supera a cualquier otro algoritmo para problemas que son suficientemente grandes, pero cuando "suficientemente grande" es tan grande que el algoritmo nunca se usa en la práctica.
¡Nuevo!!: Clases de complejidad P y NP y Algoritmo galáctico · Ver más »
Charlie Eppes
Dr. Charles Edward "Charlie" Eppes (interpretado por David Krumholtz) es un personaje ficticio, protagonista de la serie de drama policíaco..
¡Nuevo!!: Clases de complejidad P y NP y Charlie Eppes · 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 »
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!!: Clases de complejidad P y NP y Circuitos booleanos · 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!!: Clases de complejidad P y NP 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!!: Clases de complejidad P y NP y Complejidad y criptografía · Ver más »
Conjetura
Por conjetura se entiende el juicio que se forma (moral, ético o matemático) de las cosas o sucesos por indicios u observaciones.
¡Nuevo!!: Clases de complejidad P y NP y Conjetura · Ver más »
Dimensión bipartita
En los campos matemáticos de teoría de grafos y optimización combinatotria, la dimensión bipartita, o número de cubierta de bicliques de un grafo G(V,E) es el número mínimo de bicliques (es decir, subgrafos bipartitos completos), que se necesitan para cubrir todas las aristas en E. Decimos que una colección de bicliques cubriendo todas las aristas en G es una cubierta de aristas de bicliques, o a veces covertura biclique.
¡Nuevo!!: Clases de complejidad P y NP y Dimensión bipartita · Ver más »
Esquema de aproximación de tiempo polinómico
En informática, un esquema de aproximación de tiempo polinómico (PTAS) es un tipo de algoritmo de aproximación para problemas de optimización (la mayoría las veces, para problemas de optimización NP-difíciles).
¡Nuevo!!: Clases de complejidad P y NP y Esquema de aproximación de tiempo polinómico · 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 »
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!!: Clases de complejidad P y NP y Función unidireccional · Ver más »
Mario de Jesús Pérez Jiménez
Mario de Jesús Pérez Jiménez (Bollullos Par del Condado, España, 13 de noviembre de 1948) es un matemático e informático teórico español, Profesor Emérito (anteriormente, Catedrático de Universidad) en el Departamento de Ciencias de la Computación e Inteligencia Artificial de la Universidad de Sevilla, es el fundador del Grupo de Investigación en Computación Natural de la misma y miembro numerario de la Academia Europaea.
¡Nuevo!!: Clases de complejidad P y NP y Mario de Jesús Pérez Jiménez · Ver más »
Matemática discreta
La matemática discreta es un área de la matemática encargada del estudio de los conjuntos discretos: finitos o infinitos numerables.
¡Nuevo!!: Clases de complejidad P y NP y Matemática discreta · Ver más »
Número primo fuerte
En matemáticas, un número primo fuerte es un número primo con ciertas propiedades.
¡Nuevo!!: Clases de complejidad P y NP y Número primo fuerte · Ver más »
Nonograma
El nonograma, también conocido como Hanjie, Picross o Griddlers en el Reino Unido, es un rompecabezas que consiste en colorear las celdas correctas de una cuadrícula, de acuerdo con los números a los lados de la misma, con el fin de revelar una imagen oculta.
¡Nuevo!!: Clases de complejidad P y NP y Nonograma · 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 »
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!!: Clases de complejidad P y NP y P (clase de complejidad) · Ver más »
Permanente (matemáticas)
En álgebra lineal, el permanente de un matriz cuadrada es una función de la matriz similar al determinante.
¡Nuevo!!: Clases de complejidad P y NP y Permanente (matemáticas) · 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!!: Clases de complejidad P y NP y Problema de satisfacción de restricciones · Ver más »
Problema del camino más corto
En la teoría de grafos, el problema del camino más corto es el problema que consiste en encontrar un camino entre dos vértices o nodos, de tal manera que la suma de los pesos de las aristas que lo constituyen sea mínima.
¡Nuevo!!: Clases de complejidad P y NP y Problema del camino más corto · Ver más »
Problema del camino más largo
En teoría de grafos, el problema del camino más largo es, dado un grafo, encontrar un camino simple de longitud máxima.
¡Nuevo!!: Clases de complejidad P y NP y Problema del camino más largo · Ver más »
Problema del conjunto de cobertura
El problema del Set Covering, también conocido por sus siglas SCP es un problema clásico en combinatoria, ciencias de la computación y teoría de la complejidad computacional.
¡Nuevo!!: Clases de complejidad P y NP y Problema del conjunto de cobertura · 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!!: Clases de complejidad P y NP y Problema del isomorfismo de grafos · 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!!: Clases de complejidad P y NP y Problema del viajante · 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!!: Clases de complejidad P y NP y Problemas de Smale · Ver más »
Programación Semidefinida
Programación Semidefinida (SDP) es una subrama de la optimización convexa cuyo interés principal yace en la optimización de una función objetiva lineal (una función especificada por el usuario, que dicho usuario busca minimizar o maximizar) sobre la intersección del cono de matrices positivo semidefinidas con un espacio afín, i.e., un espectrahedro.
¡Nuevo!!: Clases de complejidad P y NP y Programación Semidefinida · Ver más »
Protocolo de Ko-Lee-Cheon-Hang-Park
El protocolo Ko-Lee-Hang-Park es un protocolo de clave pública que usa grupos no abelianos.
¡Nuevo!!: Clases de complejidad P y NP y Protocolo de Ko-Lee-Cheon-Hang-Park · Ver más »
Red de ordenamiento
En ciencias de la computación, una red de ordenamiento (sorting network) es un algoritmo que ordena un número fijo de valores mediante el uso de una secuencia fija de comparaciones.
¡Nuevo!!: Clases de complejidad P y NP y Red de ordenamiento · Ver más »
Richard Lipton
Richard Jay Lipton (nacido el 6 de septiembre de 1946) es un informático teórico estadounidense, decano asociado de investigación, profesor y presidente de informática Frederick G. Storey en la Facultad de informática del Instituto de Tecnología de Georgia.
¡Nuevo!!: Clases de complejidad P y NP y Richard Lipton · Ver más »
Robert M. Solovay
Robert Martin Solovay (nacido el 15 de diciembre de 1938) es un matemático estadounidense especializado en teoría de conjuntos.
¡Nuevo!!: Clases de complejidad P y NP y Robert M. Solovay · 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!!: Clases de complejidad P y NP y Teoría de la complejidad computacional · Ver más »
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.
¡Nuevo!!: Clases de complejidad P y NP y Teoría de la computación · 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!!: Clases de complejidad P y NP y Teorema de la jerarquía temporal · 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!!: Clases de complejidad P y NP y Tiempo pseudopolinómico · Ver más »
Totalmente NP-completo
En la teoría de la complejidad computacional, la fuerte NP-completitud es una propiedad de los problemas computacionales que es un caso especial de NP-completitud.
¡Nuevo!!: Clases de complejidad P y NP y Totalmente NP-completo · Ver más »
Veintiún problemas NP-completos de Karp
En teoría de complejidad computacional, los veintiún (21) problemas NP-completos de Karp son un conjunto de problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos y que cumplen la característica en común de que todos ellos pertenecen a la clase de complejidad de los NP-completos.
¡Nuevo!!: Clases de complejidad P y NP y Veintiún problemas NP-completos de Karp · Ver más »
Redirecciona aquí:
Clases de complejidad p y np, 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?.
