Here we introduce a "polynomial-time reduction," which is one in which takes polynomial time (obviously). We also introduce the notion of NP-hardness and NP-completeness. We then show that if a problem is NP-complete, and is also in P, then P = NP.
If you like this content, please consider subscribing to my channel: [ Ссылка ]
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
What is a polynomial-time reduction? (NP-Hard + NP-complete)
Теги
easy theorynp-hardnp-hard and np-complete problems and conceptsnp-hard problemsnp-completenp-complete problemspolynomial timepolynomial time reductionpolynomial time explainednp completenp complete problemsnp complete explainedcomplexity theory p and np class problemsnp hardnp hard and np complete problemsnp hard explainednp hard and np completenp reduction problemsnp reductionp versus npcomputational complexitycomplexity theory
![#846 Felix als Rasenmäher - [Deutsch lernen durch Hören] @DldH Deutsch lernen mit Geschichten #dldh](https://s2.save4k.org/pic/vDsBRkLP2g8/mqdefault.jpg)
