Projeto e Análise de Algoritmos - Aula 14 - Classes de problemas: Problemas P, NP e NP-completos

Summary

This video script introduces concepts in algorithm project analysis, focusing on problem classes: P, NP, and NP-complete. It explains optimization versus decision problems, using examples like finding the shortest path in a graph. The script delves into P as tractable decision problems and NP as decision problems with polynomial-time verifiers. It highlights NP-complete problems, which are the hardest in NP, and uses the Boolean Satisfiability Problem as an example. The video concludes with the significance of these classes in computational complexity theory and the search for efficient algorithms or approximations for NP-complete problems.

Takeaways

• 😀 The lecture introduces the concepts of optimization and decision problems, setting the stage for understanding computational complexity.
• 🔍 Optimization problems involve finding the best solution among all possible solutions, such as the shortest path in a graph.
• 🤔 Decision problems require a yes or no answer, like whether a graph contains an Eulerian circuit or a Hamiltonian cycle.
• 🏫 The lecture explains the difference between P (polynomial time solvable) and NP (nondeterministic polynomial time) problem classes.
• 🔑 NP problems have a polynomial-time verifier, meaning if a solution is provided, it can be quickly checked for correctness.
• 🔄 The concept of reduction between problems is introduced, showing that solving one problem can help solve another if they are reducible.
• 📚 The class NP-complete is defined, including problems that are in NP and for which every problem in NP can be reduced to them.
• 🌐 The satisfiability problem (SAT) is highlighted as a foundational NP-complete problem, with implications for various computational tasks.
• 🛠️ The lecture discusses the implications of P vs NP, a major unsolved question in computer science, and its impact on problem-solving efficiency.
• 🎓 The importance of understanding problem classes and complexity is emphasized for computer science students and professionals.

Q & A

What is the main topic of the video script?

The main topic of the video script is an introduction to problem classes, specifically P, NP, and NP-complete problems in the context of algorithm analysis and project management.

What are optimization problems?

Optimization problems are those where each possible solution has an associated value, and the goal is to find the best solution among all viable solutions.

Can you give an example of an optimization problem mentioned in the script?

An example of an optimization problem given in the script is finding the shortest path between two vertices in a graph, which involves minimizing the number of edges in the path.

What are decision problems?

Decision problems are those where the answer is simply yes or no, determining whether a solution exists for a given problem.

What is the difference between P and NP classes of problems?

P class consists of decision problems for which a polynomial-time algorithm exists. NP class consists of decision problems for which a polynomial-time verifier exists for 'yes' instances.

What is the significance of the P vs. NP question in computer science?

The P vs. NP question is significant because it seeks to determine whether every problem whose solution can be checked quickly (in polynomial time) can also be solved quickly. It remains one of the most important open questions in computer science.

What is an NP-complete problem?

An NP-complete problem is a problem in NP that is at least as hard as the hardest problems in NP. If an efficient algorithm for solving any NP-complete problem is discovered, it can be used to solve all problems in NP efficiently.

What is the role of reduction in problem-solving within the script's context?

Reduction is used to transform one problem into another problem for which a solution is known or believed to exist. If a problem can be reduced to an NP-complete problem, it inherits the complexity of the NP-complete problem.

How is the concept of a certificate used in the context of NP problems?

In the context of NP problems, a certificate is a piece of evidence or data that can be used to verify the solution to a problem quickly (in polynomial time).

What is the relationship between optimization problems and decision problems as discussed in the script?

The script discusses that optimization problems can be formulated as decision problems by imposing a limit on the values being optimized. This allows for the application of decision problem-solving techniques to optimization problems.

What is the significance of the Hamiltonian cycle problem in the script?

The Hamiltonian cycle problem is used as an example of a decision problem in the script. It is a classic problem in graph theory that asks whether there is a cycle that visits each vertex exactly once and is NP-complete.

Outlines

00:00

📚 Introduction to Problem Classes and P vs NP

This paragraph introduces the topic of the video, which is about problem classes in computational complexity, specifically focusing on P (polynomial time) and NP (nondeterministic polynomial time) problems. It discusses the difference between optimization problems, where the goal is to find the best solution among all possible solutions, and decision problems, which simply require a yes or no answer. Examples of these problems are given, such as finding the shortest path in a graph (optimization) and determining if there is an Eulerian circuit in a graph (decision). The paragraph sets the stage for further exploration of these concepts.

05:02

🔍 Exploring Optimization and Decision Problems

The second paragraph delves deeper into the types of problems discussed, providing more examples and explanations. It explains how optimization problems involve finding the best solution with an associated value, such as the shortest path between two vertices in a graph. Decision problems, on the other hand, are about verifying the existence of a solution, exemplified by the Eulerian circuit problem. The paragraph also introduces the concept of reducing one problem to another, which is a common technique in computational complexity theory.

10:04

🔗 Relationship Between Optimization and Decision Problems

This paragraph explores the relationship between optimization and decision problems, illustrating how an optimization problem can be reformulated as a decision problem by imposing a limit on the values being optimized. It uses the example of finding the shortest path in a graph and modifying it to a decision problem that asks whether a path with fewer than a certain number of edges exists. The paragraph emphasizes the importance of understanding these problem classes in the context of computational complexity.

15:08

🧩 P and NP Problem Classes Defined

The fourth paragraph provides a more formal definition of the P and NP problem classes. P problems are those that can be solved by a polynomial-time algorithm, while NP problems have a polynomial-time verifier for their solutions. The paragraph explains the concept of a polynomial-time algorithm and how it relates to the definition of NP problems. It also discusses the significance of the P vs NP question in computer science and how it remains an open problem.

20:10

🏁 NP-Completeness and Problem Reduction

The final paragraph introduces the concept of NP-completeness, which is a central notion in computational complexity theory. It explains that an NP-complete problem is one for which every problem in NP can be reduced to it in polynomial time. The paragraph discusses the implications of NP-completeness and how it is used to demonstrate the hardness of problems within NP. It also touches on the idea of problem reduction and how it is used to prove NP-completeness.

Keywords

💡Optimization Problem

An optimization problem is defined as a problem where each possible solution has an associated value, and the goal is to find the best solution among all of them. In the context of the video, it is used to illustrate the concept of finding a 'shortest path' in a graph, which is a classic example of an optimization problem. The script mentions finding a path between two vertices with the minimum number of edges as an example of an optimization problem.

💡Decision Problem

A decision problem is one where the answer is simply 'yes' or 'no' to a given question. The video script uses the example of determining whether a graph contains an Eulerian circuit, which is a path that visits every edge exactly once, to explain decision problems. The script also discusses the Hamiltonian circuit problem, another type of decision problem, where the task is to determine if a graph contains a circuit that visits every vertex exactly once.

💡P Class

The P class, or polynomial time class, is a set of decision problems that can be solved by an algorithm in polynomial time. The script introduces this concept by explaining that problems in P are considered 'tractable', meaning they can be solved efficiently. An example given in the video is the Eulerian circuit problem, which can be solved in polynomial time, thus belonging to the P class.

💡NP Class

The NP class, or non-deterministic polynomial time class, is a set of decision problems for which a given solution can be verified in polynomial time. The script explains that NP includes problems that may not be solvable in polynomial time, but if a solution is presented, it can be checked quickly. The Hamiltonian circuit problem is given as an example of an NP problem, which can be verified efficiently but may be difficult to solve.

💡NP-Complete

An NP-complete problem is a problem in the NP class that is at least as hard as the hardest problems in NP. The script discusses the concept of NP-completeness by explaining that if a polynomial-time solution is found for any NP-complete problem, it can be used to solve all other NP problems in polynomial time. The problem of Boolean satisfiability (SAT) is mentioned as an example of an NP-complete problem.

💡Reduction

Reduction in the context of computational problems refers to the process of transforming one problem into another problem, such that a solution to the transformed problem can be used to solve the original problem. The script uses the concept of reduction to explain how the complexity of problems can be compared and how the NP-completeness of a problem can be established by reducing other NP problems to it.

💡Polynomial-Time Algorithm

A polynomial-time algorithm is an algorithm that can solve a problem in a time that is a polynomial function of the size of the input. The script discusses the importance of polynomial-time algorithms in determining the tractability of problems within the P class and the search for such algorithms in the context of NP-complete problems.

💡Boolean Satisfiability (SAT)

Boolean satisfiability, or SAT, is a problem of determining if there exists an assignment of truth values to a set of Boolean variables such that a given Boolean formula evaluates to true. The script uses SAT as an example of an NP-complete problem and explains how it involves finding a satisfying assignment for a logical expression in conjunctive normal form.

💡Eulerian Circuit

An Eulerian circuit is a path in a graph that visits every edge exactly once and returns to the starting vertex. The script explains the Eulerian circuit as an example of a decision problem that is in the P class, where the task is to determine if a given graph has such a circuit.

💡Hamiltonian Circuit

A Hamiltonian circuit is a closed loop on a graph that visits each vertex exactly once. The script discusses the Hamiltonian circuit problem as an example of an NP problem, where the goal is to determine if a given graph contains a Hamiltonian circuit, and it is used to illustrate the concept of NP-completeness.

Highlights

Introduction to problem classes, P, NP, and NP-complete problems in the context of algorithm analysis.

Definition of optimization problems where the goal is to find the best solution among all possible solutions.

Explanation of decision problems that require a simple yes or no answer regarding the existence of a solution.

Example of an optimization problem involving finding the shortest path between two vertices in a graph.

Illustration of a decision problem with the graph Euler problem, determining if a graph has an Eulerian cycle.

Discussion on the relationship between optimization and decision problems, and how one can be formulated as the other.

Introduction of P class, which consists of decision problems that can be solved by a polynomial-time algorithm.

NP class definition, including decision problems with a polynomial-time verifier for their answers.

The significance of the polynomial-time verification in defining NP problems and its relation to Turing machines.

Explanation of how to determine if a problem belongs to NP by checking for a polynomial-time verifier.

The concept of problem reduction as a common method for solving problems by transforming one problem into another.

Properties of problem reduction, including the implications for problem complexity and solvability.

Definition of NP-complete problems and the criteria for a problem to be considered NP-complete.

Cook's theorem and the first demonstration of a problem being NP-complete through the Boolean satisfiability problem.

The use of the reduction lemma to prove the NP-completeness of other problems by reducing them to known NP-complete problems.

3-SAT problem as an example of an NP-complete problem and its demonstration of NP-completeness.

Common belief in computer science that P ≠ NP and the implications for the solvability of NP-complete problems.

Conclusion of the lecture on problem classes and the significance of understanding these concepts in algorithm analysis.

Transcripts

[Música]

ah

[Música]

hola pesos sean bienvenidos a nosa aula

número 14 de proyectos y análisis de

algoritmos esa aula fallecer un aula

introductoria sobre clases de problemas

problemas pnp y en el p completos

nos vemos trenton primero aparte de

definición de que un problema de

optimización y que un problema de

decisión y finalmente vamos a hablar

sobre las clases pnp y n p completo

estas aulas de aquí son unas aulas

introductorias

el lazo mostrar todos esos conceptos de

una manera más simplificada todos

estamos interesados en esa aula en

responder a sientes que esto es porque

algunos problemas parecen ser

computación mente más difíciles que

otros como medimos su grado de

dificultad y de un problema y cómo

podemos saber cuáles problemas pueden

ser resolví dos eficientemente o no

antes de antes de saber entonces las

clases de problemas en esa aula vamos a

hacer la presentación de dos tipos de

problemas los problemas de optimización

los problemas de decisión

que que un problema de optimización es

un problema en que cada solución posible

de un valor asociado y deseamos

encontrar la mejor solución entre todas

ellas

una verdad lo que queremos responder de

entre las soluciones viables para un

problema dado que la mejor solución

veamos un ejemplo dado un grafo y dos

vértices vive queremos encontrar un

camino de vtv que tenga un menor número

de aristas usted ya queremos saber con

qué un camino más corto supone que un

oso grafo intentó todas sus aristas una

sobra foto empezó un queremos saber con

qué un camino más corto de vtv ese sería

un problema de optimización porque hay

en sí está intentando encontrar por qué

un mejor camino consell o camino de

menor costo en este caso

tenemos también los problemas de

decisión son problemas en que las

esposas simplemente si no no todas

nuestra pregunta entera va a ser existe

una solución para ese problema para ese

problema dado que hallamos dos ejemplos

aquí el primero primero el problema de

graf o bulería no

dado un grafo existe un materia fechada

que pasa por todas las áreas

entonces estamos aquí sí

ese grafo mostrado aquí es un grafo y le

diría no no si existe tenemos que

verificar si su matriz ya fechada que

pasa por todas sus aristas nos vamos a

ver aquí

si hay en ti como si comenzamos nube a

13 0 podría pasar por esa área está

después por esa

después por esa de ésta después por esa

de ese después por esa y después por esa

de aquí a entonces existe si un materia

fechada que pasa por todas las aristas

en ese caso y veamos si en todo acontece

un mismo para otro grafo será que la

gente posee encontrar más materia

fechada que pasa por todas las aristas

como su x comenzamos aquí pasamos por

aquí pasamos por aquí por aquí por aquí

de aquí a gente no consigue pasar por

por estar esta no conseguimos pasar por

estar esto de que si intentamos varias

formas a gestión fue conseguir mismo

fase list lento ese problema en la

verdad y ese grafo euler ya no en cuanto

a ese otro grafo unwra futbolería no

euler mostró que un grafo conexo tiene

un ciclo

laureano si solamente si el y noten

vértices de grado impar vamos ver si

está aconteciendo mismo aquí nosotros

dos ejemplos todos los vértices de aquí

de ese grafo son pares tenga o par 70

por ejemplo aquí un grado de vértice

húmedo hoy es grau del vértice 2 también

es 20 es 2

un grado del vértice cuatro y dos grados

del vértice tres dedos también

entonces es un grafo y no que acontece

con ese otro grafo de aquí un vértice

cero por ejemplo no está en grado para

un grado de l-3 tengo otro betis su

vértice cuatro tenga a uno

vértice 3

varios que no tenga par por tanto el y

no es un grafo eulària no

un otro ejemplo del problema de decisión

es un problema del grafo hamilton ya no

creo que ese problema ha dado un grafo

que queremos saber si existe o no un

circuito hamilton ya no

aunque el circuito hamilton ya no en un

circuito simple es que pasa por todos

sus vértices y todo por ejemplo supone

que tenemos ese grafo aquí en las

aristas aquí están puntillas también

queremos saber si existe un circuito que

pasa por todos sus vértices son su

porque comenzamos aquí en ese vértice

aquí si seguimos hacer estos que quizá

marcada se enferme yo vemos que

conseguimos pasar por todos sus vértices

una vez

y conseguimos llegar no gratis e

iniciado que ha comenzado

de aquí sí

y un grafo hamilton ya no porque porque

existe un circuito hamilton ya no negro

beige en que los problemas de decisión

las respuestas simples mencionó

algoritmo debe responder sin uno sin en

un grafo a hamilton ya no no es un grafo

hamilton yang

existe una relación entre problemas de

optimización y problemas de decisión es

posible formular un problema de

optimización como un problema de

decisión impone un límite sobre valores

era optimizado la verdad ya se está

modificando el problema de un cierto

sector no veíamos un ejemplo

tenemos un mismo ejemplo de inicio dado

un grafo y dos vértices uribe encontrar

un camino de atv que tenga un menor

número de estas ese de aquí un problema

de optimización

si quisiera tener una versión similar a

él más que sea de decisión agente podría

colocar o si entidad un grafo y dos

vértices uribe existe un camino de vtv

que tenga menos de deixar está se está

colocando un límite paso sobre un valor

hacer optimizado que un número de

aristas es de aquí sería un problema de

decisión o algoritmo va a fallar si

existe no existe

porque que alguien si está preocupado en

definir un problema de decisión y un

problema un problema de optimización

porque porque toda esa teoría que vamos

ver hoy de manera introductoria simples

en el ellis trabajan con problemas de

decisión y no con problemas de

optimización

pensamos en todo primero a clase p

porque que da clase a clase p formada

por problemas de decisión tratables

aunque que significa tratar en ese caso

significa que el sporting se les olvidó

por un algoritmo polinomio un ejemplo de

problema de decisión trata de un ejemplo

de problema que está en la clase p

el problema del grafo eulària no porque

hay que es un problema de la clase

porque hay equipos y verificar la verdad

si hay en chip o si vas a encontrar un

algoritmo que polinomio que resuelve

problemas en sí sabe que un grafo euler

ya no

el ifai de los vértices con grau para

hacer un algoritmo

que verifique si todos sus vértices son

de grau par por ejemplo en este caso ser

y que verifique también segura fue

conexo

una u otra clase de problemas son los

problemas np a clase n p formada por

problemas de decisión que posee un

verificador polinomio para respuestas y

formalmente una verdad si esta

definición está relacionada con máquinas

de touring npd no tu conjunto de

lenguajes que pueden ser aceites en

tiempo polinomio por una máquina de

turing no determine si k

lento en pena verdad y no significa no

polinomio significa no determine si es

polinomio time

aunque vamos verificar los problemas

para saber si esa clase n p

indicar si existe un verificador

polinomio para respuesta si un

verificador polinomio para respuestas

un poquito más formalmente para para

poder definir la clase n p podríamos

hablar sin un problema de decisiones en

ep si existe un algoritmo a tau que para

cualquier instancia si su problema con

respuestas si existe un certificado

ypsilon entonces esta palabra sabe aquí

es certificado aunque a de chips y donde

volver sin y ese algoritmo a consume

tiempo polinomio x nos vamos a estar

interesados con el certificado y su

algoritmo de polinomio no tamaño de

entrada

comenzamos aquí un ejemplo pero el

problema de un grafo hamilton ya no

dada una instancia cuya esposa de cinco

meses ha dado un grafo que hamilton ya

no coge un certificado de que él y

hamilton ya no hizo que a xente vai ter

que encontrar co que un certificado

una otra cosa como que hay enchufes para

verificar si realmente hice un

certificado o no y para hacer esa

verificación hay en si está usando

tiempo polinomio hizo que tenemos que

nos preguntar

entonces llamamos para un problema del

grafo hamilton ya no

supone que posee tengo grafo

hamiltonianos y alguien falla para jose

ok un ciclo que pasa por todos sus

vértices se pega aquí la respuesta

aunque que sería eso sería un

certificado un certificado para

respuestas sin porqué 'pozo verificar si

ese conjunto de ver dice si ese ciclo

si ese ciclo es realmente

un ciclo que pasa por todos sus vértices

o no y eso puede ser verificado en

tempos polinomios y ser verificados y en

tanto que un certificado en este caso el

propio circuito hamilton ya no

un conjunto de vértices desde una tvn y

puede ser verificado en tiempo polinomio

como el hecho y verifiquen tempo

polinomio y solemos ver si el sistema

está desde una vez dos dvds a b3

etcétera etcétera dbn menos un ave

en este caso estamos viendo sin

realmente uno de un ciclo hamilton

por tanto se hacen sin control

certificado que verifica por el

polinomio aumente la respuesta sin

mancha por si falta lento que el

problema del grafo hamilton ya no está

en la clase n p

un problema fundamentado en la teoría de

la computación

demostrar si pnp este problema está

haciendo pesquisado por muchas personas

en área de computación y agentes puede

llamarse un problema de familia tanto en

varios trabajos personas y personas

trabajando neeson mining en ate ahora

consiguió demostrar que p guagua n p

otro concepto importante la reducción

entre problemas más forma común de

resolver un problema y transformarlo en

otro problema b está cuya solución es

consciente de cómo resolver ve y ahora

para resolver a desembolsar me da más

veces que encontré la solución

voy con convertir por convertir a

solución dv para una solución de a

eso de ahí trae esa idea de reducción

entón dado dos problemas hay una

reducción de árabe que denotado por s

por eso de aquí apoyo y ser reducido

apoyo ser reducido para ver en un

algoritmo un polinomio que resolver

utilizando b donde llamamos un ejemplo

acelerando cada décimo mínimo de un

vector quiero encontrar por ejemplo un

tercero un mínimo elemento de un gestor

y sus pollos es reducido a un problema

de ordenanza ose ya esposo resolver el

problema de selección de cada décimo

mínimo fácil de ordenación de un gestor

con orden un vector de menor a mayor y

hay pegó por ejemplo un tercero mínimo

elemento de ese de esto

porque estamos haciendo entonces ese

caso asensi está reduciendo a para mí si

un problema se reduce a otro problema ve

en todo y no es más difícil de resolver

lo que ve - desempeño

para seleccionar un ka décimo mínimo de

un vector

todas en chip hoy resolver ese problema

agencia falo usando problema resolviendo

problemas de orden hasta después pegando

o elemento correspondiente más a la

selección nunca decimos mínimo porque se

les olvidó por otros algoritmos así

podéis encontrar un algoritmo de orden

lineal para resolver un mismo problema

es el problema no es más difícil que el

problema de ordenación en cambio que el

problema de ordenación

la verdad hay un límite inferior pero

los problemas de ordenación en el orden

tanto

el problema de selección decimos mínimo

no es más difícil de resolver su

problema de ordenanza

existen algunas características algunas

propiedades de la reducción de apoyo se

ha reducido a b&b es un problema del

tipo p entonces también es un tipo p

tenemos aquí una otra propiedad y se

apoya y se ha reducido del tipo de

posición reducido hace en toma también

puede ser reducido

y ahora vayamos a nuestra última

definición la clase n p completo

un problema de decisión np completo

np y si para todo ve que pertenecía en

el p b posey ser reducido

ok la primera parte

más o menos simple encontrar un

verificador polinomio para respuestas y

la segunda para sí complicado porque

porque jose ten que pegar todos sus

problemas en n p intenta reducir todos

esos problemas para ese problema que nos

está tentando demostrar que en el p

completo y eso de ahí complicado

un problema

la clase en el pe completo que fue

demostrado que la clase en el pe

completo del problema de satisfacción

porque ese problema eu sigue entidad a

una expresión lógica en la forma normal

conjuntiva existe una atribución de

valores para sus variables toque un

resultado de expresión sea verdadera

aquí tenemos una expresión lógica si son

los dos y nos hizo o noches dos noches 4

y 6 1 6 2 1 6 3

esto de que está en la forma normal

conjuntiva yo tengo disfunción de

conjunción es cierto que tengo

disfunciones

de conjunciones

ok queremos saber cuáles son las

atribuciones para esas variables que

podemos hacer de modo que un resultado

de expresión completa es ella verdadera

sin colocar para allí su verdadero esa

primera cláusula de que iba a ser

verdadera sino colocar así estrés falso

en su tercer test a que su equipo es el

verdadero y estoy aquí también va a ser

verdadero

para sí soy se podría colocar cualquier

valor por ejemplo para 64 también nos

colocan fauci faus es atribución de aquí

vais con que esa cláusula seria

verdadera pueden existir otras muy

importante encontrar por lo menos suma

si no conseguía encontrar una tribu es

aún posible de modo que todo eso sellar

verdadero podemos hablar que el problema

es satisfactorio

satisfacía entonces la expresión lógica

es satisfacción es un problema de

decisión que fue demostrado que la clase

n completo

la primera demostración de completitud

fue feita por cook en 1971 el y probó

que ese problema que acaba de mostrar

para voces es un problema en el pe

completo

qué es esa profana una prueba simple

bien complicada la partida demostración

de que el problema de satisfacción y

también llamado de sap

np completo demostró sé que muchos otros

problemas también son en el p completos

como eso fue efecto

fue usado un lema seguir su lema mostrar

como demostración de un problema

de un problema a ser en el completo pues

se afecta de manera más directa

su lema se sabe un problema en el pie

completo ya que pertenece a n p sí pero

si se ha reducido a en todas np completo

entonces que está fallando una verdad y

si no se quiere demostrar que un

problema en el pie completo pero

cualquier problema que no se salva que n

p completo y falsa reducción de él y

para ua me hizo que está faltando me

produce que un problema sad

n p completo yo quiero demostrar que un

problema así también en el pp completo

entonces esa reducción de usar parece

problemas

tenemos aquí un ejemplo un problema 3 a

2 en un problema 3 a cada cláusula tengo

exactamente 3 variables en una versión

del sajjil específica en que cada

cláusula fighter tres variables cada

parte maite de tres variables será que

ese problema es tan difícil cuanto a

versionar a 22 h fue demostrado que sí

que tan difícil cuando versión grados al

cause ella fue demostrado que 3 sat

también en el p completo como que fue

mostrado eso primero fue mostrado que

utilizar

np encontrando un verificador polinomio

para respuestas y que sería en este caso

como serio certificado sería a un

conjunto de valoraciones que hacen con

que la expresión sea verdadera callasen

si verifica sí

un problema e satisfacía a partir de

esas atribuciones y un segundo paso fue

hacer la reducción de sat para trazar

fase en una transformación considerando

una cláusula de usar y construyendo una

cláusula equivalente y con una fórmula 3

al paraíso fueron introducidas nuevas

variables de esa forma fue demostrado

que utilizar

np completo

existen muchos problemas apareciendo que

son n p completos en diferentes áreas

por causa de la mayoría de los

pescadores en ciencias la computación

acredita que no hay guagua np

en general hay gente podría fallar que

un problema en el pp completo es un

problema pero comprobado que exista un

algoritmo eficiente o si hay un

algoritmo polinomio por tanto debe ser

buscar heurísticas o aproximaciones para

resolver este tipo de problemas con esto

terminamos entornos aula número 14 sobre

clases de problemas espero que ellos

estén y han gustado y también terminamos

a nosa disciplina de proyecto y análisis

de algoritmos ya te aproxima

[Música]

2

[Música]

[Música]

sí

[Música]

y

y