Clase de Nick

Clase de Nick

Clase de Nick

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 en una máquina paralela con un número polinómico de procesadores en tiempo polilogarítmico. Dicho de otra forma, un problema está en NC si existen constantes c y k tales que el problema puede ser resuelto en tiempo O((log n)c) utilizando O(nk) procesadores paralelos.

Al igual que los problemas de P pueden verse como los problemas resolubles en una máquina secuencial, los de NC pueden verse como aquellos que pueden resolverse eficientemente en una máquina paralela. NC es subconjunto de P dado que las máquinas paralelas pueden simularse con máquinas secuenciales. No se ha determinado si NC = P, pero se piensa que son clases diferentes, lo que querría decir que algunos problemas no pueden ser mejorados usando una máquina paralela. Al igual que la clase NP-completo puede verse como la clase de problemas "probablemente sin solución eficiente", la clase P-completo puede verse como la clase de problemas "probablemente no paralelizables".

Stephen Cook acuñó el término NC (Clase de Nick) en honor a Nick Pippenger, quien ha investigado los circuitos de profundidad polilogarítmica y tamaño polinómico.

Referencia

  • Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. ISBN 0195085914
Obtenido de "Clase de Nick"

Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Nick Cutter — Personaje de Primeval Primera aparición episodo 1 Última aparición Episodio 16 Información Edad 35 …   Wikipedia Español

  • Clase Canberra — El Juan Carlos I, diseño base de la clase Canberra. País productor …   Wikipedia Español

  • Nick Hornby — Nombre completo Nick Hornby Nacimiento 17 de abril de 1957 (54 años) Redhill, Surrey (Reino Unido) Ocupación Escritor …   Wikipedia Español

  • Nick Zano — at the 2010 Tribeca Film Festival Nick Zano Nombre real Nick Zano Nacimiento 8 d …   Wikipedia Español

  • Nick Carle — Nombre Nicholas Alberto Carle Nacimiento 23 de noviembre de 1981 (29 años) Sydney, Australia Nacionalidad …   Wikipedia Español

  • Clase de 1999 Parte 2 — Class of 1999 II: The Substitut Título Clase de 1999 Parte 2 Curso 1999 II:El Sustituto Ficha técnica Dirección Spiro Razatos Producción Mark Sevi …   Wikipedia Español

  • 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… …   Wikipedia Español

  • Conmutación de clase de inmunoglobulina — Mecanismo de la conmutación del cambio de clase de las inmunoglobulinas por recombinación que permite el cambio de isotipo en los linfocitos B Activados. La conmutación de clase de inmunoglobulina (o conmutación del isotipo o conmutación… …   Wikipedia Español

  • Gormiti (serie animada) — Gormiti, che Miti Título Gormiti Género Ficción Animación Heroísmo País de origen Italia Duración …   Wikipedia Español

  • NC — pude significar: Carolina del Norte (del inglés North Carolina). Clase de Nick (del inglés Nick s Class). No contesta (se emplea en encuestas). No corresponde (se utiliza en formularios y encuestas). Nomenclatura Combinada Norma Cubana Nueva… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”