{"id":560,"date":"2024-03-24T13:07:14","date_gmt":"2024-03-24T13:07:14","guid":{"rendered":"https:\/\/cyberenlightener.com\/?page_id=560"},"modified":"2025-04-19T17:30:51","modified_gmt":"2025-04-19T16:30:51","slug":"np-completeness-and-approximation-algorithms","status":"publish","type":"page","link":"https:\/\/cyberenlightener.com\/?page_id=560","title":{"rendered":"NP Completeness and Approximation algorithms"},"content":{"rendered":"\n<ul class=\"wp-block-list\">\n<li><strong>P Problems, NP Problems, NP Hard Problems, NP Complete Problems<\/strong><\/li>\n\n\n\n<li><strong>Proofs of NP Complete Problems <\/strong><\/li>\n\n\n\n<li><strong>Prove that SAT is NP Complete<\/strong><\/li>\n\n\n\n<li><strong>Prove that 3SAT is NP Complete.<\/strong><\/li>\n\n\n\n<li><strong>Prove that Clique is NP Complete<\/strong><\/li>\n\n\n\n<li><strong>Prove that Vertex Cover is NP Complete.<\/strong><\/li>\n\n\n\n<li><strong>What is Approximation Algorithms?<\/strong><\/li>\n\n\n\n<li><strong>How Approx Vertex Cover algorithm works?<\/strong><\/li>\n\n\n\n<li><strong>Prove that Approx Vertex Cover is polynomial time 2 approximation algorithm?<\/strong><\/li>\n\n\n\n<li><strong>How Approx TSP works?<\/strong><\/li>\n\n\n\n<li><strong>Approximation algorithm for Bin Packing.<\/strong><\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Prove that Approx TSP is polynomial time 2 approximation algorithm?<\/strong><\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\ud835\udc0d\ud835\udc0f \ud835\udc02\ud835\udc28\ud835\udc26\ud835\udc29\ud835\udc25\ud835\udc1e\ud835\udc2d\ud835\udc1e\ud835\udc27\ud835\udc1e\ud835\udc2c\ud835\udc2c|| \ud835\udc08\ud835\udc27\ud835\udc2d\ud835\udc2b\ud835\udc28\ud835\udc1d\ud835\udc2e\ud835\udc1c\ud835\udc2d\ud835\udc22\ud835\udc28\ud835\udc27 &amp; \ud835\udc04\ud835\udc25\ud835\udc1a\ud835\udc1b\ud835\udc28\ud835\udc2b\ud835\udc1a\ud835\udc2d\ud835\udc22\ud835\udc2f\ud835\udc1e \ud835\udc03\ud835\udc22\ud835\udc2c\ud835\udc1c\ud835\udc2e\ud835\udc2c\ud835\udc2c\ud835\udc22\ud835\udc28\ud835\udc27\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/3xs0ynFqMC8?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><figcaption class=\"wp-element-caption\"><strong>NP Completeness.<\/strong><\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Proof that 3CNF SAT is NP Complete<\/strong><\/h2>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/04\/3CNF.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Embed of 3CNF.\"><\/object><a id=\"wp-block-file--media-b76ab1a9-d9f0-4916-8c45-94b538a211ac\" href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/04\/3CNF.pdf\">3CNF<\/a><a href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/04\/3CNF.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-b76ab1a9-d9f0-4916-8c45-94b538a211ac\">Download<\/a><\/div>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Can You Prove Clique is NP Complete? Watch This Video to Find Out\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/7CPambmJWv4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><figcaption class=\"wp-element-caption\"><strong>Proof that Clique is NPC<\/strong><\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>CLEQUE, VC and Ind Set<\/strong><\/h2>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/04\/CLIQUE_VC_INDSET.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Embed of CLIQUE_VC_INDSET.\"><\/object><a id=\"wp-block-file--media-d86241df-837d-44a1-9a8f-34253329dc8c\" href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/04\/CLIQUE_VC_INDSET.pdf\">CLIQUE_VC_INDSET<\/a><a href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/04\/CLIQUE_VC_INDSET.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-d86241df-837d-44a1-9a8f-34253329dc8c\">Download<\/a><\/div>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Approximation algorithms || Approximation algorithm for vertex cover\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/QwmrTFCXKeY?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><figcaption class=\"wp-element-caption\"><strong>Approximation algorithm<\/strong><\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Theorem: Approx-Vertex-Cover is a polynomial time 2-approximation algorithm for Vertex Cover.\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/aaKpDj4d6GU?list=PLNC-2IODvQCBd3VWnwfmQW78J7pQpOW4W\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-left\"><strong>Approximation algorithm for Bin Packing<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"738\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/1-738x1024.jpeg\" alt=\"\" class=\"wp-image-566\" style=\"width:1068px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/1-738x1024.jpeg 738w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/1-216x300.jpeg 216w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/1-768x1066.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/1-1107x1536.jpeg 1107w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/1.jpeg 1153w\" sizes=\"auto, (max-width: 738px) 100vw, 738px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"717\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/2-717x1024.jpeg\" alt=\"\" class=\"wp-image-567\" style=\"width:1070px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/2-717x1024.jpeg 717w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/2-210x300.jpeg 210w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/2-768x1097.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/2-1075x1536.jpeg 1075w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/2.jpeg 1120w\" sizes=\"auto, (max-width: 717px) 100vw, 717px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"727\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/3-727x1024.jpeg\" alt=\"\" class=\"wp-image-568\" style=\"width:1068px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/3-727x1024.jpeg 727w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/3-213x300.jpeg 213w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/3-768x1082.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/3-1091x1536.jpeg 1091w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/3.jpeg 1136w\" sizes=\"auto, (max-width: 727px) 100vw, 727px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/Best-Fit-1.jpg\" alt=\"\" class=\"wp-image-594\" style=\"width:1067px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/Best-Fit-1.jpg 960w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/Best-Fit-1-300x225.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/03\/Best-Fit-1-768x576.jpg 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Learn About Approximation Algorithms for Bin Packing\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/IQrgswSkohM?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Approximation Algorithm<\/strong><\/h2>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/04\/APPROXIMATIONALGO.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Embed of APPROXIMATIONALGO.\"><\/object><a id=\"wp-block-file--media-6c6773cb-8002-456b-bfd4-8af44d8e5651\" href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/04\/APPROXIMATIONALGO.pdf\">APPROXIMATIONALGO<\/a><a href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/04\/APPROXIMATIONALGO.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-6c6773cb-8002-456b-bfd4-8af44d8e5651\">Download<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Proof that 3CNF SAT is NP Complete CLEQUE, VC and Ind Set Approximation algorithm for Bin Packing Approximation Algorithm<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"class_list":["post-560","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/560","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=560"}],"version-history":[{"count":11,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/560\/revisions"}],"predecessor-version":[{"id":1803,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/560\/revisions\/1803"}],"wp:attachment":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=560"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}