¿Qué son P, NP, NP-complete y NP-hard?

Hay dos clases de problemas, P y NP (hay muchos, muchos más, pero ignoraremos el resto aquí). Estos significan “polinomio” y “polinomio no determinista”.

Asumiendo el conocimiento de la notación big-O, continuaremos desde allí. Solicite una explicación y la tendrá.

Los problemas en P se pueden resolver mediante un algoritmo de tiempo polinómico (se ejecuta en [math] O (f (n)) [/ math], donde [math] f [/ math] es polinomial). Esto incluye cosas como clasificación y triangulación.

Los problemas en NP son verificables mediante un algoritmo de tiempo polinómico, pero no necesariamente se pueden resolver. En general, nos referimos a NP menos P, cuando decimos NP (por lo que solo son verificables). Esto significa que, dada la solución a una instancia del problema, podemos verificar que es la solución correcta en el tiempo polinomial, pero que no podríamos haberla encontrado por nuestra cuenta, en el tiempo polinomial. Un ejemplo sencillo de esto es la suma de subconjuntos: dado un conjunto de números, ¿existe un subconjunto cuya suma es cero? No hay una forma conocida de resolver este problema en tiempo polinómico, pero dada la respuesta, podemos verificar fácilmente si es correcto (el problema de decisión es un poco más difícil de ver, pero supongamos que se le da el subconjunto real).

Ahora, tenemos que discutir NP-Complete y NP-Hard, que requiere una discusión sobre la reducibilidad . Reducibilidad es la noción de que, dada una instancia de algún problema difícil, podemos construir rápidamente una instancia de algún otro problema, cuya respuesta nos ayudaría a resolver el primer problema.

La lógica típica es esta: usted afirma tener un algoritmo rápido para, por ejemplo, resolver la suma de subconjuntos. Creo una máquina que, en tiempo polinómico, toma una instancia de problema de vendedor ambulante y crea a partir de ella una instancia de suma de subconjuntos. Si puede darle a mi máquina la respuesta a esa pregunta, nuevamente, en tiempo polinómico, volverá a cambiarla en la respuesta para mi problema original de vendedor ambulante. Por lo tanto, si su algoritmo de suma de subconjuntos es realmente polinómico, entonces le agregué algunos bits adicionales y creé un algoritmo de tiempo polinómico para resolver problemas de vendedores ambulantes. Si puedo crear tal máquina, entonces crea una noción de reducibilidad, es decir, el vendedor ambulante es reducible a la suma del subconjunto, lo que indica que la suma del subconjunto es al menos tan difícil como el vendedor ambulante. Intuitivamente, uno podría imaginar que con toda la verdad universal, uno podría decir que el vendedor ambulante no tiene una solución de tiempo polinómico. En ese caso, lo anterior sería una prueba por contradicción, esa suma de subconjuntos tampoco tiene una solución de tiempo polinomial.

Ahora, podemos decir con bastante facilidad qué son NP-Complete y NP-Hard:

Si dos problemas pueden reducirse entre sí, en cierto sentido son “equivalentes”. Todos los problemas en NP que son tan equivalentes, se llaman NP-Complete .

Si hay un problema NP-Complete que puede reducirse a algún problema H, entonces H es NP-Hard . Esto significa que, en cierto sentido, H es al menos tan difícil como todos los problemas de NP-Complete, pero tenga en cuenta que no es necesario que haya una reducción de H a ningún problema de NP-Complete, por lo que H podría ser más difícil que todos Problemas de NP.

Uno prueba que un problema es NP-Hard tomando un problema NP-Complete existente (3-SAT y Travelling Salesman son mis favoritos, ya que funcionan bien para la geometría), y usándolo para generar información para su problema, de modo que una respuesta a su problema es equivalente a resolver el problema NP-Complete que eligió.

Me gustaría agregar a las respuestas existentes y también centrarme estrictamente en la clase de problemas NP-hard vs NP-complete .
La clase de problemas P y NP completa son subconjuntos de la clase de problemas NP. Se dice que un problema está en la clase de complejidad P si existe un algoritmo PTIME (tiempo de ejecución polinómico) que * resuelve * el problema.
Se dice que un problema es NP-completo si existe un algoritmo PTIME que * verifica * la solución. Sin embargo, no existe un algoritmo PTIME que garantice * resolver * el problema. Tales problemas son los más difíciles en NP y se denominan problemas NP completos.

Hay otra clase de problemas llamada NP-hard. ¿Cuál es la relación entre NP-hard y NP-complete?
Los problemas NP-hard son al menos tan difíciles como el problema más difícil en NP-complete. Cuantifiquemos la afirmación:
Suponga que tengo un problema (H) que * creo * es NP-completo (la solución es verificable en PTIME). Deje que haya un paso intermedio (subrutina S) que debe resolverse para resolver H. Si se dice que S es NP completo, entonces H es al menos tan duro como S. De hecho, H es * más duro * que S Por lo tanto, H es * más difícil * que un problema NP-completo . Por lo tanto, debe estar en una clase de complejidad propia y, por lo tanto, H pertenece a una clase conocida como la clase NP-hard. Sin embargo, tenga en cuenta que H no es * estrictamente * NP-duro. Esto nos lleva a concluir que NP-complete es una clase de problemas que caen bajo NP y NP-hard: el más difícil de los problemas de NP es NP-complete y el más difícil de NP-complete es NP-hard.

Ejemplo 1 : Consideremos la versión clásica del problema TSP (Viajero vendedor) : encuentre la distancia más corta entre dos ciudades en un mapa, de modo que el vendedor visite cada ciudad solo una vez. Este es un problema de optimización restringido. Para resolver esto, primero hay que resolver Hamiltonian Cycles. En 1972, el profesor Richard Karp demostró que los ciclos hamiltonianos son NP completos. Ahora, el TSP clásico es al menos tan difícil como un problema de NP completo. El profesor Karp demostró así la dureza NP del TSP clásico. Entonces, el TSP clásico es un problema NP-difícil. Tenga en cuenta que no es * estrictamente * NP-hard .
(Hay una versión de decisión de este problema: dada la distancia L entre dos ciudades, ¿puede dar una mejor l

Ejemplo 2 : El problema de detención es NP-hard. Dada una entrada, ¿se detendrá la máquina Turing? Una máquina de Turing puede tener una restricción para detenerse; cuando resuelve el problema de SAT, puede detenerse. La solución a SAT se puede verificar en PTIME y, por lo tanto, una vez que la máquina emite la solución correcta, se detiene. Sin embargo, SAT es un problema NP-completo. Entonces, el problema de detención * general * debería ser al menos tan difícil como el problema SAT. Por lo tanto, es un problema NP-difícil.

¿Qué es * estrictamente * un problema NP-duro? Los problemas NP-completos son problemas de optimización, búsqueda o decisión. El TSP clásico es un problema de optimización. Para que un problema sea estrictamente NP-hard no debería ser un problema de optimización / decisión / búsqueda .

Estos se refieren a cuánto tiempo tarda un programa en ejecutarse. Los problemas en la clase P se pueden resolver con algoritmos que se ejecutan en tiempo polinómico.

Digamos que tiene un algoritmo que encuentra el número entero más pequeño en una matriz. Una forma de hacerlo es iterando sobre todos los enteros de la matriz y realizando un seguimiento del número más pequeño que haya visto hasta ese momento. Cada vez que mira un elemento, lo compara con el mínimo actual y, si es más pequeño, actualiza el mínimo.

¿Cuánto tiempo lleva esto? Digamos que hay n elementos en la matriz. Para cada elemento, el algoritmo debe realizar un número constante de operaciones. Por lo tanto, podemos decir que el algoritmo se ejecuta en tiempo O (n), o que el tiempo de ejecución es una función lineal de cuántos elementos hay en la matriz. * Por lo tanto, este algoritmo se ejecuta en tiempo lineal.

También puede tener algoritmos que se ejecutan en tiempo cuadrático (O (n ^ 2)), tiempo exponencial (O (2 ^ n)) o incluso tiempo logarítmico (O (log n)). La búsqueda binaria (en un árbol equilibrado) se ejecuta en tiempo logarítmico porque la altura del árbol de búsqueda binaria es una función logarítmica del número de elementos en el árbol.

Si el tiempo de ejecución es alguna función polinómica del tamaño de la entrada **, por ejemplo, si el algoritmo se ejecuta en tiempo lineal o tiempo cuadrático o tiempo cúbico, entonces decimos que el algoritmo se ejecuta en tiempo polinómico y el problema que resuelve está en clase P.

notario público

Ahora hay muchos programas que no (necesariamente) se ejecutan en tiempo polinómico en una computadora normal, pero sí se ejecutan en tiempo polinómico en una máquina Turing no determinista. Estos programas resuelven problemas en NP , que significa tiempo polinomial no determinista. Una máquina de Turing no determinista puede hacer todo lo que una computadora normal puede hacer y más. *** Esto significa que todos los problemas en P también están en NP.

Una forma equivalente de definir NP es señalando los problemas que pueden verificarse en el tiempo polinómico. Esto significa que no hay necesariamente una forma de tiempo polinómico para encontrar una solución, pero una vez que tiene una solución, solo toma tiempo polinómico para verificar que sea correcta.

Algunas personas piensan que P = NP, lo que significa que cualquier problema que pueda verificarse en tiempo polinómico también puede resolverse en tiempo polinómico y viceversa. Si pudieran probar esto, revolucionaría la informática porque la gente podría construir algoritmos más rápidos para muchos problemas importantes.

NP-hard

¿Qué significa NP-hard? Muchas veces puede resolver un problema reduciéndolo a un problema diferente. Puedo reducir el problema B al problema A si, dada una solución al problema A, puedo construir fácilmente una solución al problema B. (En este caso, “fácilmente” significa “en tiempo polinómico”).

Si un problema es NP-hard , esto significa que puedo reducir cualquier problema en NP a ese problema. Esto significa que si puedo resolver ese problema, puedo resolver fácilmente cualquier problema en NP. Si pudiéramos resolver un problema NP-hard en tiempo polinómico, esto demostraría que P = NP.

NP-complete

Un problema es NP completo si el problema es ambos

• NP-hard, y
• en NP.

* Un punto técnico: O (n) en realidad significa que el algoritmo se ejecuta en tiempo asintóticamente lineal, lo que significa que la complejidad del tiempo se aproxima a una línea a medida que n se hace muy grande. Además, O (n) es técnicamente un límite superior, por lo que si el algoritmo se ejecutó en tiempo sublineal, aún podría decir que es O (n), incluso si esa no es la mejor descripción.

** Tenga en cuenta que si la entrada tiene muchos parámetros diferentes, como n y k, puede ser polinomial en n y exponencial en k

*** Según el comentario de Xuan Luo, las máquinas de Turing deterministas y no deterministas pueden calcular exactamente las mismas cosas, ya que cada máquina de Turing no determinista puede ser simulada por una máquina de Turing determinista (una “computadora normal”). Sin embargo, pueden calcular cosas en diferentes cantidades de tiempo.

P (problemas decidibles en tiempo polinómico) es una clase de problemas que se pueden decidir en tiempo polinómico, es decir, hay un algoritmo para dicho problema que indica si la solución de una instancia dada de un problema es verdadera / falsa en O (n ^ k ) tiempo para alguna constante k.
Por ejemplo, decidir si existe una ruta de k enlaces como máximo entre dos vértices u y v está en P.

NP (problemas determinables de tiempo de polinomio no determinista) es una clase de problemas que tienen certificados de aceptación cortos y algoritmos de verificación eficientes, es decir, dado un certificado de solución, es fácil verificar si el problema está satisfecho.
Aceptar el certificado es información que se puede usar para decidir si la respuesta es verdadera o falsa.
Formalmente, hay un problema en NP si existe un algoritmo de verificación A tal que para cualquier entrada x para la que la respuesta sea “verdadera”, haya un certificado c tal que | c | es polinomial y A (x, c) = verdadero. Para cualquier x para la que la respuesta sea verdadera, no existe un certificado c tal que | c | es polinomial y A (x, c) es verdadero.
Por ejemplo, dado un gráfico G y un número k, decidir si existe una camarilla (subgrafo completo) de tamaño k, está en NP.

P es un subconjunto de NP, es decir, cualquier problema que esté en P también está en NP. Es fácil ver que para cualquier problema que pueda decidirse en tiempo polinómico, existe un algoritmo de verificación que dado cualquier certificado simplemente ignora el certificado y devuelve el resultado del algoritmo de tiempo polinómico.

Si NP es también un subconjunto de P (es decir, P = NP) es una pregunta abierta. Nadie lo sabe todavía.

NP-hard es una clase de problemas que son los más difíciles de todos en NP. Estos son los problemas de tal manera que si podemos resolverlos rápidamente, entonces podemos resolver todos los problemas en NP rápidamente y P sería igual a NP. Los problemas NP-hard pueden ser de cualquier tipo: problemas de decisión, problemas de búsqueda o problemas de optimización, por lo que es posible que ni siquiera estén en NP.
Por ejemplo, el problema de la camarilla discutido anteriormente es NP-duro.

NP-complete es una clase de problemas que están en NP y NP-hard. Los problemas de NP completo se transforman entre sí mediante reducciones de tiempo polinomial de muchos, por lo que si existe un algoritmo de tiempo polinomial para cualquiera de ellos, entonces existen algoritmos polinomiales para todos ellos. Sin embargo, todavía no se ha encontrado ningún algoritmo polinómico para ningún problema de NP completo.
Por ejemplo, el problema de la camarilla discutido anteriormente es NP-completo.

Para profundizar en la teoría de la complejidad, consulte este curso sobre udacity:
Introducción al curso teórico de informática (CS313)

El concepto ha sido muy bien explicado por Jessica Su.

Agregando a su respuesta, solo para ayudar a visualizar esto mejor:

Como se mencionó, P es un subconjunto de NP, y la intersección de NP y NP-hard es NP-completa.

La caja de forma ovalada sería una si P = NP = NP-completo.

Si P = NP se demostrara cierto, habría muchas consecuencias serias en el mundo real. Todos los esquemas de cifrado conocidos se basan en el hecho de que los factores primos de grandes números son algo que puede verificarse de manera factible pero no calcularse. Si P = NP, eso significa que también habría formas factibles de calcular factores primos y, por lo tanto, descifrar códigos sin sus claves privadas.

Relacionado con esto, citando al científico informático del MIT Scott Aaronson:

Si P = NP, entonces el mundo sería un lugar profundamente diferente de lo que generalmente suponemos. No habría ningún valor especial en los “saltos creativos”, no habría una brecha fundamental entre resolver un problema y reconocer la solución una vez que se encuentre. Todos los que pudieran apreciar una sinfonía serían Mozart; todos los que pudieran seguir un argumento paso a paso serían Gauss; todos los que puedan reconocer una buena estrategia de inversión serían Warren Buffett. Es posible poner el punto en términos darwinianos: si este es el tipo de universo que habitamos, ¿por qué no habríamos evolucionado para aprovecharlo?

Aquí está la mejor explicación laica que he encontrado.

Supongamos que tenemos un gran grupo de estudiantes que necesitamos emparejar para trabajar en proyectos. Sabemos qué estudiantes son compatibles entre sí y queremos ponerlos en grupos compatibles de dos. Podríamos buscar todas las parejas posibles, pero incluso para 40 estudiantes tendríamos más de 300 mil millones de billones de parejas posibles.

En 1965, Jack Edmonds dio un algoritmo eficiente para resolver este problema de coincidencia y sugirió una definición formal de ” cálculo eficiente ” (ejecuta a tiempo un polinomio fijo del tamaño de entrada). La clase de problemas con soluciones eficientes se conocería más tarde como P para ” Tiempo polinomial “.

Pero muchos problemas relacionados no parecen tener un algoritmo tan eficiente. ¿Qué pasaría si quisiéramos hacer que grupos de tres estudiantes con cada par de estudiantes en cada grupo sean compatibles ( Partición en triángulos )? ¿Qué pasaría si quisiéramos encontrar un gran grupo de estudiantes que sean compatibles entre sí ( Clique )? ¿Qué pasaría si quisiéramos sentar a los estudiantes alrededor de una gran mesa redonda sin estudiantes incompatibles sentados uno al lado del otro ( Ciclo Hamiltoniano )? ¿Qué pasa si ponemos a los estudiantes en tres grupos para que cada estudiante esté en el mismo grupo con solo sus compatibles ( 3-Coloring )?

Todos estos problemas tienen un sabor similar: dada una posible solución, por ejemplo, una tabla de asientos para la mesa redonda, podemos validar esa solución de manera eficiente. La colección de problemas que tienen soluciones verificables de manera eficiente se conoce como NP (por ” Tiempo polinomial no determinista “).

Llamamos a los problemas NP más difíciles (que incluyen Partición en triángulos, Clique, Hamiltonian Cycle y 3-Coloring) ” NP-complete “, es decir, dado un algoritmo eficiente para uno de ellos, podemos encontrar un algoritmo eficiente para todos ellos y de hecho cualquier problema en NP. Steve Cook, Leonid Levin y Richard Karp desarrollaron la teoría inicial de la completitud NP que generó múltiples premios ACM Turing. En la década de 1970, los científicos teóricos informáticos Garey y Johnson mostraron cientos de problemas más cuando NP-complete.

NP-hard es una clase de problemas que son al menos tan difíciles como los problemas más difíciles en NP.

Ahora, un poco de antecedentes sobre el santo grial (la pregunta de $ 1 millón) – ¿P = NP?

• Verdadero (la respuesta de $ 6 millones): P = NP significa que por cada problema que tiene una solución verificable eficientemente, también podemos encontrar esa solución eficientemente.
• Falso: P ≠ NP significa que es imposible encontrar un algoritmo general que resuelva de manera correcta y precisa un problema de NP completo todo el tiempo.

Referencia :
Lance Fortnow, ” El estado del problema P versus el problema NP “, Comunicaciones de la ACM, vol. 52 No. 9, páginas 78-86, septiembre de 2009.

Si todavía está confundido, podría deberse a algunas suposiciones que está haciendo de manera incorrecta / sin saberlo.

Para aclarar:

NP: no significa polinomio no polinómico sino polinomio no determinista
NP y NP Complete son un problema de decisión (Sí o No)
NP: Dado un problema que la máquina de turing no determinista resuelve en tiempo polinómico, y su solución, ¿puede verificarlo? en tiempo polinómico si la solución es correcta?
NP completo: ¿Es este un problema de NP disfrazado? Es decir, dado un problema NP, ¿puedo transformarlo en otro problema NP en tiempo polinómico ? El significado de esto es que si puedo resolver un problema NP Complete en tiempo polinomial, entonces puedo resolver todos los problemas NP Complete en tiempo polinomial.
NP Hard: no necesariamente problemas de decisión ‘Más difícil’ que el problema NP . ¿Por qué? Debido a que puede haber algún problema NP Hard cuya solución no se puede verificar en tiempo polinómico (ver NP más arriba). Estos son los problemas que se pueden transformar a partir de un problema NP Complete en tiempo polinómico. El significado de esto es que si puedo resolver el problema NP Hard en tiempo polinomial, entonces puedo 1) resolver todos los problemas NP Hard en tiempo polinomial y 2) resolver todos los problemas NP Complete en tiempo polinomial (pero lo inverso no es cierto). De esta manera, puedo resolver todos los problemas de NP en tiempo polinómico. Sin embargo, si puedo resolver todos los problemas de NP en tiempo polinómico, entonces no necesariamente significa que pueda resolver todos los problemas de NP Hard en tiempo polinómico. ¿Por qué? debido a que un problema NP Hard puede ser tal que, dada su solución, puede que no haya una verificación polinómica (un requisito para NP )

Primero, comprendamos qué es NP. Supongamos que te topas con un rompecabezas de Sudoku que parece que no puedes resolver. Entonces, un amigo se acerca a ti y se jacta: “¡Jaja! ¡Sé la respuesta al problema!” Sorprendido, le dices a tu amigo: “¡Pruébalo!” Tu amigo llena los espacios vacíos en tu rompecabezas de Sudoku, y he aquí, con un vistazo rápido, has verificado que la respuesta es correcta. “¿Cómo hiciste eso?” le preguntaste a tu amigo. Él responde: “No importa;)”

Sudoku es un problema de NP porque puede verificar “rápidamente” una solución a un problema de Sudoku. (Por “rápidamente”, realmente me refiero a “en tiempo polinomial”). No importa si realmente puede resolver la solución rápidamente o no. Lo único que importa para que un problema esté en NP es si una solución se puede verificar rápidamente.

Ahora, pasemos a los problemas NP-Hard. Al mirar su rompecabezas de Sudoku, se pregunta: “Bueno, no puedo resolver los rompecabezas de Sudoku rápidamente … ¡¡Pero qué pasaría si tuviera una habilidad mágica para resolver instantáneamente cualquier rompecabezas de Sudoku en un abrir y cerrar de ojos !!!” La respuesta a este “qué pasaría si” es bastante buena. Resulta que si tuvieras la habilidad mágica de resolver cualquier rompecabezas de Sudoku al instante, ¡también puedes usar esta habilidad para resolver (no solo verificar) cualquier problema de NP rápidamente (en tiempo polinómico)! Por ejemplo, dada la capacidad de resolver acertijos de Sudoku al instante, puedes usar esta habilidad mágica para ayudarte a descubrir rápidamente si un juego FreeCell es realmente completable. (Tenga en cuenta que esto puede no ser muy “fácil” de hacer, pero los científicos informáticos han demostrado que es posible , que es lo único que importa).

Por lo tanto, Sudoku está en NP-Hard. En resumen, un problema NP-Hard es un problema tal que, dada la habilidad mágica de resolverlo instantáneamente, puede usar esta habilidad para resolver cualquier problema NP rápidamente.

Entonces esta es la versión simple de la definición de NP-Hard. Pero, ¿por qué “duro”? Bueno, si lo piensas bien, los problemas NP-Hard son bastante poderosos en el sentido de que si puedes resolverlos mágicamente, las posibilidades son infinitas. Por supuesto, si un problema es muy “poderoso”, entonces no esperarías que sea fácil de resolver, ¿verdad? Por el contrario, los problemas fáciles, como la suma, no le otorgan mucha potencia en el sentido de que poder realizar la suma al instante realmente no ayuda a resolver otros problemas de NP rápidamente. Entonces, problemas poderosos, como el Sudoku, son al mismo tiempo muy difíciles de resolver, de ahí el término NP-Hard.

Nota al pie: Sudoku también está en NP-Complete. La única diferencia entre NP-Hard y NP-Complete es que los problemas de NP-Complete también deben ser problemas de NP, pero los problemas de NP-Hard no tienen esta restricción.

Mi objetivo es proporcionar la intuición para esta pregunta ya que otras respuestas hicieron un buen trabajo al describir los términos técnicos.

Considere un escenario en el que entre a la sala de examen y tenga las siguientes tres preguntas:

1. ¿Existe [matemática] x [/ matemática] en el conjunto [matemática] \ {1, 2, \ puntos, 1000 \} [/ matemática] tal que [matemática] x * x = 300 [/ matemática]?
2. ¿Existe [matemática] x, y, z [/ matemática] en el conjunto [matemática] \ {1, 2, \ puntos, 10 \} [/ matemática] tal que [matemática] x * y * z + x * y ^ 3 * z + 17 * x * y * z ^ 2 = 4564 [/ matemáticas]?
3. ¿Existen [matemática] a, b, c [/ matemática] en el conjunto [matemática] \ {1, 2, \ puntos, 10 \} [/ matemática] tal que [matemática] 17 * a * b * c ^ 2 + a * b * c + a * b ^ 3 * c = 4564 [/ matemáticas]?

Mientras revisa estas preguntas, siente que la primera pregunta es fácil pero las dos últimas son difíciles . ¿Qué quieres decir exactamente con fácil o difícil? Ambos son términos relativos y vagos, ¿verdad? ¿Podemos etiquetar los problemas que son realmente fáciles (o factibles) y que son difíciles (no factibles)?

Antes de comenzar, supongamos dos cosas:

1) No eres menos que Arthur T. Benjamin [1] y puedes hacer cualquier cálculo en un segundo sin importar lo complicado que sea.
2) ¡No sabes cosas complicadas como smare-root de raíz cuadrada!

Con esto comienzas a resolver la primera pregunta. Su enfoque es simple y robusto: probar todos los valores posibles de [math] x [/ math]. Entonces hay 1000 valores posibles para probar. Tiempo estimado para resolver este problema: 1000 segundos. Pero te das cuenta de que [matemáticas] x [/ matemáticas] tiene que serlo incluso si esperas satisfacer la ecuación. ¡Guay! Ahora tiene solo 500 posibilidades para probar. Tiempo estimado para resolver el problema: 500 segundos. Otra comprensión es que [matemática] x ^ 2 [/ matemática] aumenta a medida que sigues aumentando [matemática] x [/ matemática] y recuerdas que 20 * 20 = 400. Por lo tanto, si existe una solución, debería estar dentro de los primeros 20 números. Ahora solo necesita verificar 20 posibilidades. Tiempo estimado para resolver el problema: 20 segundos. ¡Guauu! Esto es 50 veces mejor que el enfoque ingenuo.

Ahora pasemos a la segunda pregunta. Considere [math] (x, y, z) [/ math] como una tupla. Dado que cada elemento en la tupla puede tomar cualquier valor entre 1 y 10, tenemos 1000 de estas posibles tuplas. Todavía necesita solo un segundo para verificar si [matemática] x * y * z + x * y ^ 3 * z + 17 * x * y * z ^ 2 [/ matemática] es de hecho igual a 4564 para [matemática] dada ( x, y, z) [/ matemáticas]. Tiempo estimado para resolver el problema – 1000 seg. Casi no hay esperanza de reducir este tiempo. No hay ninguna propiedad o estructura especial que pueda explotar para reducir el número de posibilidades de la tupla (y, por lo tanto, el tiempo para resolver) de manera significativa .

No dispuesto a desperdiciar tus 1000 segundos en la segunda pregunta, recurres a la tercera. Una vez más se encuentra con las mismas dificultades, pero se da cuenta de que si pudiera resolver la segunda pregunta, también podrá resolver la tercera. Puede cambiar el nombre de algunas variables, reorganizar algunos términos y se ve exactamente como el segundo problema.

Entonces, al darte cuenta de que ahora solo tienes un problema que resolver, diriges tu atención a la segunda pregunta. Como el tiempo corre, no puedes explorar todas las posibilidades. Ahora tiene dos opciones: puede pedirle a la persona que está sentada a su lado la solución y le dice la solución, diga [matemáticas] (x, y, z) = (3, 5, 2) [ /mates]. En lugar de simplemente copiar su solución, la verifica en un segundo. Tenga en cuenta que no puede resolver el problema en un segundo, pero si alguien le proporciona la solución, puede verificarlo en un segundo. Esto es posible porque él / ella ha hecho todo el trabajo duro (parte creativa) y usted simplemente lo está verificando.

Si sus valores morales no le permiten copiar, puede adoptar el siguiente enfoque. Adivina los valores de [math] (x, y, z) [/ math] y verifica la solución. Entonces su papel borrador para la Pregunta 2 se ve así

• (1a posibilidad) – (4, 8, 2)
• (2ª posibilidad) – (3, 9, 13)
• …

y así sucesivamente, a diferencia de la pregunta 1 donde parece

• (1a posibilidad) – 1
• (Segunda posibilidad) – 2
• …

Puede predecir con certeza cuál es la próxima posibilidad para la Pregunta 1 (y, por lo tanto, el enfoque determinista ), pero no para la Pregunta 2 (enfoque no determinista ). Estas dos palabras se usan en el mismo contexto al definir P y NP .

En general, etiquetamos (¡no dividimos!) Todos los problemas con dos etiquetas. Primero, donde puede encontrar la solución en un tiempo razonable , la llamamos clase P. Segundo, donde solo puede verificar la solución en un tiempo razonable proporcionado por otra persona. Llamamos a esa clase NP . Observe que la clase P está contenida en la clase NP y, por lo tanto, decimos etiqueta sobre división.

Entonces la pregunta 1 está en P (y también en NP ) y las preguntas 2 y 3 están en NP (pero pueden no estar en P ). Esto se debe a una segunda suposición. Por favor ver nota al pie.

Ahora es un desafío abierto es resolver todos los problemas en NP en un tiempo razonable . Y en la búsqueda de un millón de dólares [2], usted y yo comenzamos a atacar todos los problemas que se conocen en NP . Pero es una tontería atacar cientos de problemas a la vez, ¿verdad? Así que decidimos elegir el problema más difícil en este mundo y poner toda nuestra energía en resolver ese problema. El conjunto de problemas tan difíciles se llama NP-Hard . Pero espera, estamos haciendo este asunto más complicado de lo necesario. Si pudiéramos elegir el problema más difícil en la clase NP y resolverlo, podríamos resolver muchos problemas que son menos difíciles que eso y están en NP . La clase de tales problemas se llama NP-Complete . Entonces, puedo decir vagamente, la pregunta 2 está en NP-Complete ya que una vez que resuelves eso, la pregunta 3 es fácil.

Pero, ¿por qué debería preocuparse por la clasificación en primer lugar?

Como los recursos son limitados, no desea asignarlos a algún problema que requiera mucho tiempo. Si no le importa esto, podría perderse tratando de resolver el segundo problema perdiendo puntos para las tres preguntas.

Nota –
Técnicamente, 2 y 3 NO están en NP si incluye herramientas algebraicas. El enfoque P vs NP en el círculo matemático ruso consistía en verificar si un problema dado puede resolverse sin explorar (casi) todas las posibilidades. En este sentido, podemos clasificar las preguntas 2 y 3 en NP .

Referencias
1 Página de inicio de Arthur Benjamin
2 Instituto de Matemáticas Clay

NP: polinomio no determinista: significa que un problema en NP puede resolverse utilizando una máquina no determinista en tiempo polinomial.
Esto significa aproximadamente que si tiene un número infinito de máquinas (computadoras [más rigurosamente, máquinas de Turing]), puede adivinar la solución para cada solución posible y pedirle a cada máquina que verifique esa solución (lo que lleva tiempo polinómico para esta clase de problemas).

Tenga en cuenta que todos los problemas en P están en NP.

NP-Complete: si tiene una solución a un problema (típicamente de decisión) y la solución puede verificarse en tiempo polinomial, pero NO puede encontrar una solución en tiempo polinomial, entonces se dice que el problema es NP-complete.

Por ejemplo, supongamos que le preguntamos si se puede lograr un valor de V en el problema de la mochila con un peso determinado W de la mochila, no puede encontrar una solución rápidamente, pero si le doy un posible conjunto de artículos {… }, puede verificar si es una solución válida que tiene el valor V y se ajusta al peso W. Por lo tanto, el problema de la mochila de decisión es NP-completo.

NP-Hard: si tiene una solución a un problema (típicamente de optimización) y la solución ni siquiera puede verificarse en tiempo polinómico (y mucho menos resolverlo en tiempo polinomial), entonces se dice que el problema es NP-hard.

Por ejemplo, supongamos que afirmo que {…} es la mejor solución para el problema de la mochila. ¿Es posible que lo verifiques rápidamente? No, ya que tendrías que resolver la mochila para ver si puedes encontrar una mejor solución, y resolver la optimización de la mochila es NP-hard.

Los problemas de P son preguntas que tienen una respuesta de sí / no y que una computadora puede resolver fácilmente.
Por ejemplo, determinar si un número es primo es un problema relativamente fácil de resolver.

Los problemas de NP son preguntas que tienen respuestas sí / no que son fáciles de verificar, pero que son difíciles de resolver. Y por duro, quiero decir que su computadora tardaría años, décadas o siglos en encontrar una respuesta.
Por ejemplo, el problema del vendedor ambulante es tratar de descubrir el viaje más corto a través de un montón de ciudades, visitando cada ciudad solo una vez.

Los problemas NP completos son tipos especiales de problemas NP. Puede tomar cualquier tipo de problema NP y torcerlo y retorcerlo hasta que parezca un problema NP completo.
Por ejemplo , el problema de la mochila es NP. Puede preguntar cuál es la mejor manera de llenar una mochila si tenía muchas piezas de diferentes tamaños de metales preciosos en el suelo, y que no puede llevarlas todas en la bolsa.
(La mochila también tiene NP completo, ¡así que también puedes hacer lo contrario!)

Los problemas NP-Hard son peores que los problemas NP. Incluso si alguien le sugiriera una solución a un problema NP-Hard, todavía llevaría una eternidad verificar si tenían razón.
Por ejemplo, en un vendedor ambulante, tratar de descubrir el camino más corto absoluto a través de 500 ciudades en su estado tomaría una eternidad en resolver. Incluso si alguien se acercara a usted y le diera un itinerario y afirmara que era el camino más corto, le tomaría una eternidad descubrir si era un mentiroso o no.

P: problemas que pueden resolverse en tiempo polinómico. por ejemplo Ordenando puedes resolverlo en O (n log n).

NP: problemas de decisión que pueden verificarse en tiempo polinómico. por ejemplo Hamiltonian Path (Cycle). Para el problema de Hamiltonian Path, suponga que tiene una solución como Sí o No, luego verifique si es correcta, se puede hacer en tiempo polinómico.

NP-Hard: si todos los problemas en NP pueden reducirse al problema X, entonces X es NP Hard.

NP-Complete: problemas que son NP Hard y en NP.

Todavía se desconoce si P = NP o P! = NP. Probar cualquiera de los dos gana $ 1000000
premio en efectivo. Pero se cree ampliamente que P! = NP.

Como ingeniero de software, conocer esta información es útil por la siguiente razón: ¡Suponga que tiene un problema y no conoce su NP-C, PERDERÁ mucho tiempo tratando de encontrar un tiempo polinómico o una buena solución!

Son todos conjuntos de conjuntos.

De hecho, son conjuntos de conjuntos de números naturales.

En la teoría de los cálculos, un problema es un conjunto de números naturales. Resolver un problema significa que hay un algoritmo que proporciona miembros de ese conjunto. Verificar una solución significa que, dado un número natural, hay un algoritmo que indica si pertenece a ese conjunto o no. Por ejemplo,

CUADRADOS = { n [matemáticas] \ epsilon [/ matemáticas] N : n es un cuadrado perfecto}

PRIMES = { n [matemáticas] \ epsilon [/ matemáticas] N : n es un número primo}

Son problemas. ¿Notaste algo? Denoté los 3 conjuntos de números naturales con MAYÚSCULAS en negrita .

Una forma de comparar algoritmos es ver cuántos pasos computacionales (es tiempo para computadoras y robots) deben hacer los algoritmos frente a cuántos dígitos tienen las entradas. Si se nos pidiera competir en la multiplicación de dos números de tamaño (# de dígitos) my k resp. y el tuyo dio m + k pasos y el mío necesitaba m elevado a k pasos, ¡entonces el tuyo es superior! Diríamos que su algoritmo escala linealmente el tamaño de entrada de wrt y el mío es exponencial . (Así que hay algoritmos que se escalan polinomialmente y luego hay algoritmos que son solo pruebas de existencia existence

Tiempo de definiciones:

(Conjuntos de conjuntos de números naturales en MAYÚSCULAS en negrita y cursiva ).

Se dice que un problema que puede resolverse en tiempo polinómico es P.

Se dice que un problema cuya solución puede verificarse como correcta o incorrecta en el tiempo polinómico, una vez que alguien ya ha proporcionado la solución tentativa, se dice que pertenece a NP . Por supuesto, si puede resolver un problema, puede verificar una solución, entonces P [math] \ subset [/ math] NP .

Un problema cuyo complemento está en NP es CONP .

Un problema está en NPHARD si el mismo problema en NP puede “reducirse” a ese problema. (Esto parece ser lo opuesto a “reducción”, además de que tendría que tomar pasos computacionales para reducirlo, por lo que es un requisito que la reducción en sí misma sea polinómica). Esto incluye problemas que pueden estar en NP y superiores.

La intersección de NP y NPHARD se llama NPCOMPLETE , porque son geniales. Todos los problemas en NP se pueden convertir a cualquier problema en NPCOMPLETE , incluidos ellos mismos. Resuelve solo uno de ellos en polytime y habrás probado P = NP .

Ahora para algunos ejemplos:

PRIMES está en P.

El objetivo de encontrar la ruta más corta a través de cada ciudad y regresar a la ciudad inicial, llamada el problema del vendedor ambulante, está en NP .

Probar tautologías en lógica proposicional es CONP . Ver sistemas de prueba proposicional.

¡Super Mario Bros. es NPCOMPLETE , y también The Legend of Zelda!

Reducción de los artículos de Wikipedia y arxiv a una respuesta de Quora: NPOE . [cita requerida]

PD. ¡Espero que mis lectores más pedantes disculpen mi falta de formalismo!

P: problemas que pueden resolverse en tiempo polinómico. por ejemplo Ordenando puedes resolverlo en O (n log n).

NP: problemas de decisión que pueden verificarse en tiempo polinómico. por ejemplo Hamiltonian Path (Cycle). Para el problema de Hamiltonian Path, suponga que tiene una solución como Sí o No, luego verifique si es correcta, se puede hacer en tiempo polinómico.

NP-Hard: si todos los problemas en NP pueden reducirse al problema X, entonces X es NP Hard.

NP-Complete: problemas que son NP Hard y en NP.

Todavía se desconoce si P = NP o P! = NP. Probar cualquiera de los dos gana $ 1000000
premio en efectivo. Pero se cree ampliamente que P! = NP.

Como ingeniero de software, conocer esta información es útil por la siguiente razón: ¡Suponga que tiene un problema y no conoce su NP-C, PERDERÁ mucho tiempo tratando de encontrar un tiempo polinómico o una buena solución!

Para resolver la relación de recurrencia anterior, solo tiene que usar el teorema maestro. Puedes ver eso
a = 4, b = 4, f (n) = nlogn = (n ^ c) (log ^ kn), donde c = k = 1
log a a base b = log4 a base 4 = 1 = c
Entonces, su caso 2 del teorema maestro, que da
T (n) = Θ (n ^ c) (log ^ k + 1 n) = Θ (n ^ 1) (log ^ 2 n) = Θ (n log ^ 2 n)

Para comprender las clases NP Complete y NP Hard, debe tener una comprensión básica de un par de cosas.

Un problema de decisión es un problema que siempre puede responder “sí” o “no”. Por ejemplo, “¿Tienes un hermano?”. Siempre puede responder “sí” o “no” para tales preguntas. Tales problemas son lo que llamamos problemas de decisión.

Una máquina determinista de Turing es la máquina a la que estamos acostumbrados normalmente. Una computadora es una máquina de Turing determinista. Una máquina de Turing no determinista es una máquina que viene con paralelismo ilimitado. Por ejemplo, si llega a una bifurcación en una carretera, puede tomar la carretera izquierda o la carretera derecha. Así es como funciona la máquina determinista de Turing. Pero como la máquina de Turing no determinista tiene un paralelismo ilimitado, puede tomar ambos caminos. Es similar a ejecutar múltiples subprocesos en una computadora. Las máquinas de Turing no deterministas no pueden realizarse en la práctica.

Un problema de decisión está en la clase P , si podemos resolver el problema en tiempo polinómico usando una máquina de Turing determinista. Significa que podemos resolver el problema muy rápidamente. Terminará el problema en algún momento n ^ k, donde k es alguna constante. Por ejemplo, encontrar el elemento max en una matriz, verificar si una cadena es palíndromo o no, verificar si un número es primo o no, y así sucesivamente.

Un problema de decisión está en la clase NP , si podemos resolverlo en tiempo polinómico usando una máquina de Turing no determinista para obtener la respuesta “sí” a su problema. (La respuesta “no” se considera en clase co-NP). Eso significa que no podemos resolver el problema en tiempo polinómico usando una máquina de Turing determinista. Pero siempre podemos verificar si nuestra solución es correcta en el tiempo polinómico. Entonces, si alguien le da un problema NP y la respuesta es “sí”, podemos verificar si la respuesta es correcta o no en el tiempo polinómico. Pero tenga en cuenta que no podemos encontrar la respuesta en el tiempo polinómico (solo verifique si la respuesta es correcta).

Un problema X está en NP-Completo si podemos probar que está en NP y que podemos reducir un problema NP conocido Y a X en tiempo polinómico, es decir, podemos resolver rápidamente Y si sabemos cómo resolver rápidamente X. Significa que si alguien descubre una solución de tiempo polinomial para cualquier problema NP-Complete, entonces cada problema NP puede resolverse en tiempo polinomial. Esto demostrará que P = NP. Por ejemplo: 3-SAT (conjunción de disyunciones de 3 cláusulas), problema del Buscaminas. Cada problema de NP puede reducirse a un problema de 3 SAT (Teorema de Cook)

Un problema está en NP-Hard si y solo si es “al menos tan” difícil como un problema de NP. La definición formal es que un problema X está en NP-Hard si hay un problema NP-Completo Y de tal manera que Y pueda reducirse a X en tiempo polinómico. Pero dado que cualquier problema NP-Completo puede reducirse a cualquier otro problema NP-Completo en tiempo polinómico, todos los problemas NP-Completo pueden reducirse a cualquier problema NP-Completo en tiempo polinomial. Entonces, si hay una solución para un problema NP-Hard en tiempo polinómico, hay una solución para todos los problemas NP en tiempo polinómico. Los problemas NP-completos también son NP difíciles. Además, los problemas NP-Hard pueden no estar en NP, lo que significa que pueden no tener soluciones que puedan verificarse en tiempo polinómico. Por ejemplo: problema de detención (dado un programa P y entrada I, ¿se detendrá? No está en NP), versión de optimización de TSP (necesitamos encontrar un cronograma real; más difícil que la versión de decisión de TSP). Los problemas NP-Hard pueden no ser un problema de decisión

Creo que la base principal para comprender la “dureza” del problema es comprender el objetivo detrás de la necesidad de categorización.
Nuestro objetivo es:
(a) Dado un problema, quiero saber todas las soluciones
(b) Ante un problema y ante una solución, verifique si la solución es correcta.

Ahora, suponga que hay un algoritmo ideado para un problema.
Un algoritmo se puede definir como un conjunto de instrucciones que se ejecutan (condicionalmente) en función de un conjunto de variables y reglas (imagen de un diagrama de flujo)

Si este algoritmo se ejecuta y resuelve (a), entonces la salida del algoritmo es una solución, si el algoritmo es para (b), entonces la salida es ‘sí’ o ‘no’.

Una máquina de Turing es una representación de este algoritmo, que (puede o no) toma entrada, ejecuta el algoritmo y da salida (tiene un estado final), es decir, termina.

Ahora, el algoritmo que se ejecuta y produce una solución, se llama Máquina Determinista de Turing (DTM), ya que el estado final de proporcionar la solución es determinista.

Pero, si un algoritmo podría tomar múltiples caminos al llegar a una solución (s) y el camino elegido para llegar a la solución no puede establecerse de manera determinista, es una máquina de Turing no determinista (NTM). Hay una clase de problemas que pueden resolverse si agotamos todos los caminos posibles (imaginemos un árbol de estados posibles) y llegamos a una solución. Se sabe que se resuelven usando un NTM.
Es fácil ver que una NTM puede expresarse como una DTM.

Ahora que la máquina está lista, debemos preocuparnos por cuánto tiempo nos tomamos para encontrar una solución.
Si el tiempo que toma se basa en el tamaño de entrada, y el tiempo se puede expresar como una ecuación polinómica que involucra el tamaño de entrada, se puede decir que el algoritmo se puede resolver en tiempo polinómico.
Y el conjunto de problemas que se pueden resolver utilizando un DTM en tiempo polinómico se agrupan en la clase P.

Los problemas, que se pueden resolver utilizando NTM en tiempo polinomial, se agrupan NP (máquina de turing no determinista en tiempo polinomial). Como discutimos acerca de los algoritmos que se ajustan a la NTM, no son fáciles de resolver en tiempo polinómico. Y, por lo tanto, P = NP hace una pregunta si los problemas de NP pueden resolverse en tiempo polinómico como P.

Como otros explicaron anteriormente, los problemas de NP completo son los que pueden resolverse usando las soluciones de otros problemas de NP en tiempo polinómico. Por lo tanto, si tenemos una solución para uno, podemos usarlo para resolver el otro (en tiempo polinómico). Y dada esta propiedad, si encontramos el problema máximo ‘más difícil’ que es NP completo, podremos resolver todos los problemas de NP. Y estos se llaman problemas NP-hard.
Es fácil ver que si podemos resolver un problema NP-difícil, entonces todos los problemas NP pueden resolverse en tiempo polinómico, y por lo tanto P = NP.

Nota: La mayoría usa la clase NP para denotar problemas de decisión, pero no se limita a eso.

Creo que esta sería una respuesta muy concisa. Por favor, consulte:

Observe cómo la dificultad aumenta de arriba a abajo: cualquier NP se puede reducir a NP-Complete , y cualquier NP-Complete se puede reducir a NP-Hard , todo en tiempo P (polinomial).

Si puede resolver una clase de problema más difícil en el tiempo P, eso significará que encontró cómo resolver todos los problemas más fáciles en el tiempo P (por ejemplo, demostrando P = NP, si descubre cómo resolver cualquier problema NP-Complete en P tiempo).

  ____________________________________________________________
 El |  Tipo de problema |  Verificable en tiempo P |  Soluble en tiempo P |  Dificultad creciente
 ___________________________________________________________ |  El |
 El |  P |  Sí |  Sí |  El |
 El |  NP |  Sí |  Sí o no * |  El |
 El |  NP-Complete |  Sí |  Desconocido |  El |
 El |  NP-Hard |  Sí o no ** |  Desconocido *** |  El |
 ____________________________________________________________ V

Notas sobre entradas Yes o No :

• * Un problema NP que también es P se puede solucionar en tiempo P.
• ** Un problema NP-Hard que también es NP-Complete es verificable en tiempo P
• *** NP-Complete problemas (todos los cuales forman un subconjunto de NP-hard) podrían ser. El resto de NP difícil no lo es.

También encontré este diagrama bastante útil para ver cómo todos estos tipos se corresponden entre sí (preste más atención a la mitad izquierda del diagrama).

Muchas personas ya han aclarado la diferencia en otras preguntas relacionadas. Pero, en caso de que no lo hayan ayudado, aquí hay una explicación en términos simples:

Se dice que un problema está en la clase P si hay un algoritmo de tiempo polinómico para resolver el problema. Además, también puede verificar * una solución en tiempo polinómico para todos los problemas de la clase P.

Se dice que un problema está en la clase NP si puede verificar * una solución en tiempo polinómico, pero aún no sabe si puede resolverlo con un algoritmo de tiempo polinómico.

* Por verificación quiero decir: si un Oracle presenta una solución a un problema, puede verificar si la solución es correcta o no en tiempo polinómico.

Permítanme tratar de decirlo de esta manera: los problemas en la clase NP son en su mayoría problemas naturales cuya solución intelectualmente “más vaga” implica pasar por todas las combinaciones de valores posibles de las variables de decisión involucradas. ¡Esta solución perezosa para el hombre es, por supuesto, la más difícil para su esclavo, la máquina! Si bien cada uno de esos problemas tiene una estructura intrínseca, su estructura no se ha explorado a fondo (excepto en algunos casos especiales) para ser utilizada en general como base para construir algoritmos más inteligentes que perezosos. Queremos decir con: “más inteligente que perezoso” aquellos Algoritmos que toman un número polinómico de pasos con respecto a la longitud de sus entradas. Sin embargo, este no es el final de la historia: se ha descubierto un fenómeno interesante llamado integridad (la dureza es similar, pero no exactamente la misma) que básicamente dice que todos esos problemas tienen la misma estructura de uno más básico, llamado SAT. SAT plantea una pregunta eterna sobre si el valor de verdad de una oración en el sistema lógico más básico conocido en las edades modernas (el cálculo proposicional) puede deducirse sin recurrir a través de todas las posibilidades de valores de verdad de las variables.

¿Dónde en todo esto se encuentra el determinismo (es decir, el comportamiento causal) y el no determinismo (es decir, el comportamiento sin causa única) de los algoritmos? En realidad es fácil de entender. Cuando la gente no pudo explorar la estructura de esos problemas naturales mencionados anteriormente y, por lo tanto, tuvo que vivir con la idea de que la solución perezosa podría ser la única posible en máquinas normales, imaginó un modelo teórico de máquinas en el que una solución se calcula “de alguna manera” sin la necesidad de explicar por qué. Las máquinas reales son, por supuesto, causales, es decir, cualquier paso es causado por uno y solo un paso anterior que proporciona, por lo tanto, siempre una explicación de lo que sucede y por qué. Calcular la solución “de alguna manera” tenía una ventaja muy importante: podía usarse para eliminar el requisito de pasar por todos los valores de combinación sin explicar por qué o cómo se hace esto 🙂 … Entonces, una máquina que trabaja en un modo “sin causa única” resuelve los problemas naturales anteriores de una manera inteligente, “de alguna manera”! Esto explica por qué también se les llama problemas en NP (la clase de algoritmos polinomiales no deterministas), mientras que los algoritmos inteligentes usuales están en DP (la clase de algoritmos polinomiales deterministas).

¿Por qué dije problemas “naturales”? No solo porque están ocurriendo en la naturaleza, sino también porque ocasionalmente son resueltos por la naturaleza de una manera rápida. Entonces, cuando las matemáticas hacen la pregunta de si NP = P en realidad también pregunta: “¿No es determinismo o determinismo lo que la naturaleza usa cuando resuelve esos problemas?”, Llevando esta pregunta a un nivel completamente diferente de discusión, ya que, como ya sabrá Una pregunta muy similar está en el corazón de la física moderna y muchos grandes científicos, incluido Einstein, se negaron a aceptar cualquier modelo no determinista que describa la naturaleza del cerebro.

¿Cuál es la diferencia entre “sin causa única” y “sin causa alguna”? El primero incluye la posibilidad de que muchas cosas causen lo que está sucediendo (sin que sepamos realmente cuál es el responsable), mientras que el segundo: “Sin causa” significa, al menos en teoría, una aleatoriedad verdadera. ¿Hay clases de algoritmos aleatorios? ¿Qué queremos decir con un algoritmo “aleatorio”? ¿No es la aleatoriedad verdadera algo que derrota la mera idea de un Algoritmo? E incluso si admitimos que existen Algoritmos aleatorios (al exigir que se arrojen monedas antes de tomar decisiones, por ejemplo): ¿son más poderosas que las no deterministas o deterministas? ¿La naturaleza usa algoritmos aleatorios cuando resuelve los problemas anteriores? Esto se formaliza en la pregunta si P = BPP o no (BPP es la gran clase de Algoritmos aleatorios). En realidad, también se sabe que si P = NP, entonces también P = BPP, que básicamente dice que si rompemos el rompecabezas de “estructura” anterior, los mundos causales y no causales colapsan en uno. Como puede ver, el problema de NP está relacionado con algunas cosas profundas. :)))

Sorprendentemente, el consenso entre las personas con CS ahora es que ambos: P <> NP y P = BPP, lo que significa: Aunque muchos parecen creer que no tiene sentido explorar la estructura de los problemas naturales anteriores porque el no determinismo es más poderoso que el determinismo, ven aleatoriedad , que es la mejor manera de hacer “de alguna manera” las cosas, ser tan poderoso como el determinismo. Extraño … no? :))))) – Saludos