As I’ve mentioned in the past, complexity theory isn’t really one of my favorite topics. As a professional computer scientist, knowing and loving complexity up to the level of NP-completeness
\nis practically a requirement. But once you start to get beyond P and NP, there are thousands of complexity classes that have been proposed for one reason or another, and really understanding all of them can get remarkably difficult, and what’s worse, can feel like an utterly pointless exercise,
\nparticularly if the writer\/teacher you’re learning from isn’t very good.<\/p>\n
I’m not going to write a long series of posts on the more esoteric complexity classes. But there
\nare a few that are interesting, and might even have some relevance to actual practical problems in
\nselecting algorithms for a software system.<\/p>\n
<\/p>\n
Today I’m going to talk about one of those practical classes, called BPP. BPP is the class of This is going to sound like a strange idea, but it’s actually quite useful. A probabilistic machine Why is this useful?<\/p>\n Randomized algorithms are something we use in the real world. It’s rare that we can accurately The most common kind of probabilistic algorithm is called a Monte Carlo<\/em> algorithm. The The easiest example of this is one of the common algorithms for rapidly determining whether a A slightly harder example of a probabilistic algorithm is one of the classic NP hard<\/em> problems There’s a P-time probabilistic algorithm for the TSP based on a randomized heuristic which (Note: The above explanation around the TSP was originally wrong. I managed to make There are also a couple of other interesting complexity classes that are related to BPP:<\/p>\n As I’ve mentioned in the past, complexity theory isn’t really one of my favorite topics. As a professional computer scientist, knowing and loving complexity up to the level of NP-completeness is practically a requirement. But once you start to get beyond P and NP, there are thousands of complexity classes that have been proposed for […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[80],"tags":[],"class_list":["post-268","post","type-post","status-publish","format-standard","hentry","category-computational-complexity"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-4k","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/268","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=268"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/268\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=268"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=268"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=268"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nproblems that can be solved on a probabilistic machine in P-time with a bounded probability<\/em> of
\nless than 1\/2 of generating an incorrect result. (In general, we use 1\/3 as the probability of failure,
\nbut that’s just for convenience; you can pick any<\/em> bound b you want from the range 0 < b
\n< 1\/2, and you’ll wind up with the same<\/em> set of problems in BPP.) <\/p>\n
\nis one which can, whenever it needs to during the execution of its program, flip a coin to select one
\nof two paths. If you can write a program which uses these random branches, and which will on average
\ngenerate correct results for better than 2 out of 3 executions, then the program is considered a
\ncorrect<\/em> probabilistic solution to the problem, and the problem that it solves in in BPP.<\/p>\n
\ncharacterize the precise probability of generating a successful result, but BPP provides a model that
\nallows us to describe the capabilities of algorithms that use randomness. And even in cases where we
\ndon’t really use randomness, we often approach exponential-time problems using heuristics – essentially
\nguesses about how to find a solution that work most<\/em> of the time. To get some sense of what
\nbenefit we can get from heuristics, we can model them as probabilistic branches – so again, BPP gives
\nus a way of exploring what the heuristics can do to the worst-case performance for a problem.<\/p>\n
\nidea of a Monte Carlo algorithm is pretty simple. Imagine that you’ve got a barn with a target painted
\non it, and your goal is to have a blind man put a bullet through the target. A Monte Carlo approach is
\nbasically handing him a rapid-fire machine gun, pointing him in the right general direction, and having
\nhim pull the trigger while moving the gun barrel back and forth until he’s fired a couple of hundred
\nshots. There’s a pretty good chance that at least one of those shots will wind up in the target. In
\na Monte Carlo algorithm, you use some form of making a series of random guesses, each of which eliminates a group of possible solutions. After enough tries, whatever’s left is probably right.<\/p>\n
\nnumber is prime. Given an integer N which you think might be prime, randomly pick 10000 integers
\nbetween 2 and N1\/2<\/sup>. For each one, check if it divides N evenly. If none of them divide it,
\nthen there’s a high probability that it’s prime. <\/p>\n
\nis called the traveling salesman problem (TSP). In the TSP, you are a salesman who is given a route
\nincluding a set of N cities (nodes). You know the distance between any two cities in the list. The question is: what is the shortest path that allows you to visit all of the cities? <\/p>\n
\ngenerates an optimal solution with high probability. Basically, generate a random path. Then randomly pick a group of four nodes that are close together, and randomly rearrange them. If the
\nresult is a shorter path, then that becomes the new path. If after some number *N* tries, the path doesn’t improve, then stop. (There are more details than that, but that’s the basic idea.) This algorithm can run in P-time, and generates optimal results with extremely high probability for problem sizes in the millions<\/em> of nodes – problem sizes which would be absolutely intractable using
\nany conventional deterministic algorithm. It’s not guaranteed to generate a correct result; and in fact, I’ve
\nnever seen an analysis that manages to specifically pin down its rate of success. But in practice,
\nits results are astonishingly good; I don’t think that for any test on hundreds on thousands of nodes where we know the correct answer that this algorithm didn’t find it.<\/p>\n
\na major error in saying that the TSP was NP-complete. The TSP is not<\/b> NP-complete;
\nit is NP-hard which is quite a lot worse. The TSP decision problem<\/b> in NP-complete. The decision problem is: Given a path-length P, is there<\/em> a path whose length is less than or equal to P? Just that decision part is NP-complete. Generating a path as a solution is quite a lot harder; well into EXP territory, even if it turns out that P=NP.)<\/em><\/p>\n\n
\n– that is, problems which take an input, and return “Yes” or “No”. A problem is in RP if
\nthere’s a probabilistic machine that always<\/em> answers “No” if the correct answer
\nis “No”, and returns “Yes” more than 50% of the time if the correct answer is “Yes”. (What
\nthis means is sort of the opposite of what it sounds like: if it answers “Yes”,
\nthen it’s always right. If it answers “No”, then there’s some chance that it was
\nwrong.) We know that P ⊆ RP, and RP ⊆ BPP. (There was originally a type in this paragraph, where I wrote “A problem is in NP” where it correctly reads “A problem is NP”. Thanks to commenter Coin for the catch!)<\/em><\/li>\n
\ndecision problems. For a problem in PP, there is
\na polynomial-time probabilistic algorithm where if the correct answer is “Yes”, the
\nalgorithm will answer “Yes” more than<\/em> half the time; if the correct answer
\nis “No”, it will answer “Yes” less than<\/em> half the time. BPP ⊆ PP; PP
\nis a much weaker (in the sense of the strength of results required) class – an
\nalgorithm in PP can end up arbitrarily close to being correct as often as
\na coin-flip, no matter how many times you repeat the computation; whereas in BPP,
\nthere is a probability bound, and by running the computation multiple times, you
\ncan reduce the bound to get arbitrarily close to always being correct. In fact,
\nit turns out that NP ⊆ PP.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"