{"id":10601,"date":"2017-03-29T13:44:39","date_gmt":"2017-03-29T13:44:39","guid":{"rendered":"https:\/\/www.techopedia.com\/definition\/non-deterministic-algorithm\/"},"modified":"2019-08-29T17:08:36","modified_gmt":"2019-08-29T17:08:36","slug":"non-deterministic-algorithm","status":"publish","type":"definition","link":"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm","title":{"rendered":"Non-Deterministic Algorithm"},"content":{"rendered":"<h2><span id=\"what_does_non-deterministic_algorithm_mean\">What Does Non-Deterministic Algorithm Mean?<\/span><\/h2>\n<p>A non-deterministic algorithm can provide different outputs for the same input on different executions. Unlike a deterministic algorithm which produces only a single output for the same input even on different runs, a non-deterministic algorithm travels in various routes to arrive at the different outcomes.<\/p>\n<p>Non-deterministic algorithms are useful for finding approximate solutions, when an exact solution is difficult or expensive to derive using a deterministic algorithm.<\/p>\n<h2><span id=\"techopedia_explains_non-deterministic_algorithm\">Techopedia Explains Non-Deterministic Algorithm<\/span><\/h2>\n<p>One example of a non-deterministic algorithm is the execution of concurrent algorithms with race conditions, which can exhibit different outputs on different runs. Unlike a deterministic algorithm which travels a single path from input to output, a non-deterministic algorithm can take many paths, with some arriving at the same outputs, and others arriving at different outputs. This feature is mathematically used in non-deterministic computation models like non-deterministic finite automaton.<\/p>\n<p>A non-deterministic algorithm is capable of execution on a deterministic computer which has an unlimited number of parallel processors. A non-deterministic algorithm usually has two phases and output steps. The first phase is the guessing phase, which makes use of arbitrary characters to run the problem.<\/p>\n<p>The second phase is the verifying phase, which returns true or false for the chosen string. There are many problems which can be conceptualized with help of non-deterministic algorithms including the unresolved problem of P vs NP in computing theory.<\/p>\n<p>Non-deterministic algorithms are used in solving problems which allow multiple outcomes. Every outcome the non-deterministic algorithm produces is valid, regardless of the choices made by the algorithm during execution.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>What Does Non-Deterministic Algorithm Mean? A non-deterministic algorithm can provide different outputs for the same input on different executions. Unlike a deterministic algorithm which produces only a single output for the same input even on different runs, a non-deterministic algorithm travels in various routes to arrive at the different outcomes. Non-deterministic algorithms are useful for [&hellip;]<\/p>\n","protected":false},"author":7813,"featured_media":0,"comment_status":"open","ping_status":"closed","template":"","format":"standard","meta":{"_acf_changed":false,"_lmt_disableupdate":"","_lmt_disable":"","om_disable_all_campaigns":false,"footnotes":""},"definitioncat":[241,216],"class_list":["post-10601","definition","type-definition","status-publish","format-standard","hentry","definitioncat-computer-science","definitioncat-software-development"],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v23.8 (Yoast SEO v23.8) - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>What is a Non-Deterministic Algorithm? - Definition from Techopedia<\/title>\n<meta name=\"description\" content=\"This definition explains the meaning of Non-Deterministic Algorithm and why it matters.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Non-Deterministic Algorithm\" \/>\n<meta property=\"og:description\" content=\"This definition explains the meaning of Non-Deterministic Algorithm and why it matters.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm\" \/>\n<meta property=\"og:site_name\" content=\"Techopedia\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/techopedia\/\" \/>\n<meta property=\"article:modified_time\" content=\"2019-08-29T17:08:36+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:site\" content=\"@techopedia\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm#article\",\"isPartOf\":{\"@id\":\"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm\"},\"author\":{\"name\":\"Margaret Rouse\",\"@id\":\"https:\/\/www.techopedia.com\/#\/schema\/person\/f5dd538e31ee352d105b8af36c4268a5\"},\"headline\":\"Non-Deterministic Algorithm\",\"datePublished\":\"2017-03-29T13:44:39+00:00\",\"dateModified\":\"2019-08-29T17:08:36+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm\"},\"wordCount\":262,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/www.techopedia.com\/#organization\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm#respond\"]}],\"articleSection\":\"\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm\",\"url\":\"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm\",\"name\":\"What is a Non-Deterministic Algorithm? - Definition from Techopedia\",\"isPartOf\":{\"@id\":\"https:\/\/www.techopedia.com\/#website\"},\"datePublished\":\"2017-03-29T13:44:39+00:00\",\"dateModified\":\"2019-08-29T17:08:36+00:00\",\"description\":\"This definition explains the meaning of Non-Deterministic Algorithm and why it matters.\",\"breadcrumb\":{\"@id\":\"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.techopedia.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Software Development\",\"item\":\"https:\/\/www.techopedia.com\/topic\/2\/software-development\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Term\",\"item\":\"https:\/\/www.techopedia.com\/definition\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Non-Deterministic Algorithm\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.techopedia.com\/#website\",\"url\":\"https:\/\/www.techopedia.com\/\",\"name\":\"Techopedia\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/www.techopedia.com\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.techopedia.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/www.techopedia.com\/#organization\",\"name\":\"Techopedia\",\"url\":\"https:\/\/www.techopedia.com\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.techopedia.com\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/www.techopedia.com\/wp-content\/uploads\/2023\/08\/techopedia-light.svg\",\"contentUrl\":\"https:\/\/www.techopedia.com\/wp-content\/uploads\/2023\/08\/techopedia-light.svg\",\"width\":209,\"height\":37,\"caption\":\"Techopedia\"},\"image\":{\"@id\":\"https:\/\/www.techopedia.com\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/techopedia\/\",\"https:\/\/x.com\/techopedia\",\"https:\/\/www.linkedin.com\/company\/techopedia\/\",\"https:\/\/www.youtube.com\/c\/Techopedia\"],\"publishingPrinciples\":\"https:\/\/www.techopedia.com\/about\/editorial-policy\",\"ownershipFundingInfo\":\"https:\/\/www.techopedia.com\/about\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.techopedia.com\/#\/schema\/person\/f5dd538e31ee352d105b8af36c4268a5\",\"name\":\"Margaret Rouse\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.techopedia.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/www.techopedia.com\/wp-content\/uploads\/2023\/02\/margaret-rouse-headshot.jpeg\",\"contentUrl\":\"https:\/\/www.techopedia.com\/wp-content\/uploads\/2023\/02\/margaret-rouse-headshot.jpeg\",\"caption\":\"Margaret Rouse\"},\"description\":\"Margaret is an award-winning writer and educator known for her ability to explain complex technical topics to a non-technical business audience. Over the past twenty years, her IT definitions have been published by Que in an encyclopedia of technology terms and cited in articles in the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine, and Discovery Magazine. She joined Techopedia in 2011. Margaret\u2019s idea of \u200b\u200ba fun day is to help IT and business professionals to learn to speak each other\u2019s highly specialized languages.\",\"sameAs\":[\"https:\/\/www.linkedin.com\/in\/margaretrouse\/\",\"https:\/\/x.com\/https:\/\/twitter.com\/@techdefinitions\"],\"knowsAbout\":[\"Technology expert\"],\"url\":\"https:\/\/www.techopedia.com\/contributors\/margaret-rouse\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"What is a Non-Deterministic Algorithm? - Definition from Techopedia","description":"This definition explains the meaning of Non-Deterministic Algorithm and why it matters.","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:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm","og_locale":"en_US","og_type":"article","og_title":"Non-Deterministic Algorithm","og_description":"This definition explains the meaning of Non-Deterministic Algorithm and why it matters.","og_url":"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm","og_site_name":"Techopedia","article_publisher":"https:\/\/www.facebook.com\/techopedia\/","article_modified_time":"2019-08-29T17:08:36+00:00","twitter_card":"summary_large_image","twitter_site":"@techopedia","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm#article","isPartOf":{"@id":"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm"},"author":{"name":"Margaret Rouse","@id":"https:\/\/www.techopedia.com\/#\/schema\/person\/f5dd538e31ee352d105b8af36c4268a5"},"headline":"Non-Deterministic Algorithm","datePublished":"2017-03-29T13:44:39+00:00","dateModified":"2019-08-29T17:08:36+00:00","mainEntityOfPage":{"@id":"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm"},"wordCount":262,"commentCount":0,"publisher":{"@id":"https:\/\/www.techopedia.com\/#organization"},"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm#respond"]}],"articleSection":""},{"@type":"WebPage","@id":"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm","url":"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm","name":"What is a Non-Deterministic Algorithm? - Definition from Techopedia","isPartOf":{"@id":"https:\/\/www.techopedia.com\/#website"},"datePublished":"2017-03-29T13:44:39+00:00","dateModified":"2019-08-29T17:08:36+00:00","description":"This definition explains the meaning of Non-Deterministic Algorithm and why it matters.","breadcrumb":{"@id":"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.techopedia.com\/definition\/24618\/non-deterministic-algorithm#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.techopedia.com\/"},{"@type":"ListItem","position":2,"name":"Software Development","item":"https:\/\/www.techopedia.com\/topic\/2\/software-development"},{"@type":"ListItem","position":3,"name":"Term","item":"https:\/\/www.techopedia.com\/definition"},{"@type":"ListItem","position":4,"name":"Non-Deterministic Algorithm"}]},{"@type":"WebSite","@id":"https:\/\/www.techopedia.com\/#website","url":"https:\/\/www.techopedia.com\/","name":"Techopedia","description":"","publisher":{"@id":"https:\/\/www.techopedia.com\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.techopedia.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/www.techopedia.com\/#organization","name":"Techopedia","url":"https:\/\/www.techopedia.com\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.techopedia.com\/#\/schema\/logo\/image\/","url":"https:\/\/www.techopedia.com\/wp-content\/uploads\/2023\/08\/techopedia-light.svg","contentUrl":"https:\/\/www.techopedia.com\/wp-content\/uploads\/2023\/08\/techopedia-light.svg","width":209,"height":37,"caption":"Techopedia"},"image":{"@id":"https:\/\/www.techopedia.com\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/techopedia\/","https:\/\/x.com\/techopedia","https:\/\/www.linkedin.com\/company\/techopedia\/","https:\/\/www.youtube.com\/c\/Techopedia"],"publishingPrinciples":"https:\/\/www.techopedia.com\/about\/editorial-policy","ownershipFundingInfo":"https:\/\/www.techopedia.com\/about"},{"@type":"Person","@id":"https:\/\/www.techopedia.com\/#\/schema\/person\/f5dd538e31ee352d105b8af36c4268a5","name":"Margaret Rouse","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.techopedia.com\/#\/schema\/person\/image\/","url":"https:\/\/www.techopedia.com\/wp-content\/uploads\/2023\/02\/margaret-rouse-headshot.jpeg","contentUrl":"https:\/\/www.techopedia.com\/wp-content\/uploads\/2023\/02\/margaret-rouse-headshot.jpeg","caption":"Margaret Rouse"},"description":"Margaret is an award-winning writer and educator known for her ability to explain complex technical topics to a non-technical business audience. Over the past twenty years, her IT definitions have been published by Que in an encyclopedia of technology terms and cited in articles in the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine, and Discovery Magazine. She joined Techopedia in 2011. Margaret\u2019s idea of \u200b\u200ba fun day is to help IT and business professionals to learn to speak each other\u2019s highly specialized languages.","sameAs":["https:\/\/www.linkedin.com\/in\/margaretrouse\/","https:\/\/x.com\/https:\/\/twitter.com\/@techdefinitions"],"knowsAbout":["Technology expert"],"url":"https:\/\/www.techopedia.com\/contributors\/margaret-rouse"}]}},"_links":{"self":[{"href":"https:\/\/www.techopedia.com\/wp-json\/wp\/v2\/definition\/10601"}],"collection":[{"href":"https:\/\/www.techopedia.com\/wp-json\/wp\/v2\/definition"}],"about":[{"href":"https:\/\/www.techopedia.com\/wp-json\/wp\/v2\/types\/definition"}],"author":[{"embeddable":true,"href":"https:\/\/www.techopedia.com\/wp-json\/wp\/v2\/users\/7813"}],"replies":[{"embeddable":true,"href":"https:\/\/www.techopedia.com\/wp-json\/wp\/v2\/comments?post=10601"}],"version-history":[{"count":0,"href":"https:\/\/www.techopedia.com\/wp-json\/wp\/v2\/definition\/10601\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.techopedia.com\/wp-json\/wp\/v2\/media?parent=10601"}],"wp:term":[{"taxonomy":"definitioncat","embeddable":true,"href":"https:\/\/www.techopedia.com\/wp-json\/wp\/v2\/definitioncat?post=10601"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}