{"id":14983,"date":"2022-10-09T23:13:09","date_gmt":"2022-10-09T17:43:09","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/"},"modified":"2022-10-09T23:13:09","modified_gmt":"2022-10-09T17:43:09","slug":"solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/","title":{"rendered":"[Solved] Is there any NP example that we can get an answer in polynomial time\uff1f [closed]"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

Disclaimer: This answer focuses on the practical aspects of dealing with the fact that there are problems for which no polynomial-time algorithm is known. To give an answer that is precise from a theoretical point of view, the terminology used in the question is not clear enough.<\/em><\/p>\n

There are two meanings of NP in computer science that are easily mixed up.<\/p>\n

(1) NP as the class of NP complete problems:<\/p>\n

For none of these problems, a polynomial algorithm has been found so far. It has been proven that if such an algorithm is found for one of these problems, each of them can be solved in polynomial time. The standard example for NP completeness is the Travelling Salesman problem.<\/p>\n

(2) NP as a property of an algorithm that requires exponential time:<\/p>\n

Any NP algorithm can be solved for small sizes N. The issue is just that the number of calculations increases exponentially (i.e. very<\/em> quickly) with N.<\/p>\n

There are problems for which originally only NP algorithms have been known but for which polynomial time algorithms have been found later. Unfortunately I cannot come up with an example right now.<\/p>\n

For many problems that have only NP solutions, there exist polynomial time algorithms that produce good approximations of the optimal solutions. For many applications this is sufficient.<\/p>\n<\/p><\/div>\n

<\/div>\n<\/div>\n

4<\/span> <\/p><\/div>\n<\/div>\n

[ad_2]<\/p>\n

solved Is there any NP example that we can get an answer in polynomial time\uff1f [closed] <\/p>\n","protected":false},"excerpt":{"rendered":"

[ad_1] Disclaimer: This answer focuses on the practical aspects of dealing with the fact that there are problems for which no polynomial-time algorithm is known. To give an answer that is precise from a theoretical point of view, the terminology used in the question is not clear enough. There are two meanings of NP in … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[457,3897,3898],"class_list":["post-14983","post","type-post","status-publish","format-standard","hentry","category-solved","tag-algorithm","tag-np","tag-np-hard"],"yoast_head":"\n[Solved] Is there any NP example that we can get an answer in polynomial time\uff1f [closed] - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time\uff1f-closed\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] Is there any NP example that we can get an answer in polynomial time\uff1f [closed] - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] Disclaimer: This answer focuses on the practical aspects of dealing with the fact that there are problems for which no polynomial-time algorithm is known. To give an answer that is precise from a theoretical point of view, the terminology used in the question is not clear enough. There are two meanings of NP in ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time\uff1f-closed\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-10-09T17:43:09+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] Is there any NP example that we can get an answer in polynomial time\uff1f [closed]\",\"datePublished\":\"2022-10-09T17:43:09+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/\"},\"wordCount\":249,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"algorithm\",\"np\",\"np-hard\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/\",\"name\":\"[Solved] Is there any NP example that we can get an answer in polynomial time\uff1f [closed] - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-10-09T17:43:09+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] Is there any NP example that we can get an answer in polynomial time\uff1f [closed]\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] Is there any NP example that we can get an answer in polynomial time\uff1f [closed] - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time\uff1f-closed\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] Is there any NP example that we can get an answer in polynomial time\uff1f [closed] - JassWeb","og_description":"[ad_1] Disclaimer: This answer focuses on the practical aspects of dealing with the fact that there are problems for which no polynomial-time algorithm is known. To give an answer that is precise from a theoretical point of view, the terminology used in the question is not clear enough. There are two meanings of NP in ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time\uff1f-closed\/","og_site_name":"JassWeb","article_published_time":"2022-10-09T17:43:09+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] Is there any NP example that we can get an answer in polynomial time\uff1f [closed]","datePublished":"2022-10-09T17:43:09+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/"},"wordCount":249,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["algorithm","np","np-hard"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/","url":"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/","name":"[Solved] Is there any NP example that we can get an answer in polynomial time\uff1f [closed] - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-10-09T17:43:09+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-is-there-any-np-example-that-we-can-get-an-answer-in-polynomial-time%ef%bc%9f-closed\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] Is there any NP example that we can get an answer in polynomial time\uff1f [closed]"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/14983","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=14983"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/14983\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=14983"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=14983"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=14983"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}