Projeto e Análise de Algoritmos - Aula 14 - Classes de problemas: Problemas P, NP e NP-completos
Summary
TLDRThis 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
📚 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.
🔍 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.
🔗 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.
🧩 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.
🏁 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.
Mindmap
Keywords
💡Optimization Problem
💡Decision Problem
💡P Class
💡NP Class
💡NP-Complete
💡Reduction
💡Polynomial-Time Algorithm
💡Boolean Satisfiability (SAT)
💡Eulerian Circuit
💡Hamiltonian Circuit
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
浏览更多相关视频
P, NP, NP Hard and NP Complete Problem | Reduction | NP Hard and NP Compete | Polynomial Class
Algorithm Design | Approximation Algorithm | Vertex Cover Problem #algorithm #approximation
P vs. NP: The Biggest Puzzle in Computer Science
L-1.1: Introduction to Algorithm & Syllabus Discussion for GATE/NET & Placements Preparation | DAA
Algorithm Design | Approximation Algorithm | Traveling Salesman Problem with Triangle Inequality
What is Heuristic in AI | Why we use Heuristic | How to Calculate Heuristic | Must Watch
5.0 / 5 (0 votes)