tag:blogger.com,1999:blog-6555947.post5473788006395218559..comments2023-03-24T07:33:48.282-06:00Comments on The Geomblog: Minimum language complexity needed to construct exponential time algorithmSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-6555947.post-61740123204207403762012-06-09T04:27:15.764-06:002012-06-09T04:27:15.764-06:00I suggest that you look at type lambda calculi [1]...I suggest that you look at type lambda calculi [1] that correspond to constructive logics via the Curry-Howard correspondence [2]. They do not allow to type the Y-combinator and other related combinators. They generally enables us express superexponential algorithms, and there's a rich theory of exactly what can be expressed in these calculi.<br /><br />[1] http://www.rbjones.com/rbjpub/logic/cl/tlc001.htm<br />[2] http://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondenceAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-53575851298003307022012-06-06T04:26:56.009-06:002012-06-06T04:26:56.009-06:00Well, WHILE programs (afaik a standard model of co...Well, <a href="http://cs.stackexchange.com/a/995/98" rel="nofollow">WHILE programs</a> (afaik a standard model of computation) are Turing complete and don't provide recursion, so you can obviously express exponential (and worse) algorithms in it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-20233139054700374872012-06-01T20:42:18.022-06:002012-06-01T20:42:18.022-06:00Maybe the point should be that almost any recursiv...Maybe the point should be that almost any recursive algorithm an undergraduate writes will be exponential time.Sashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-88391073758638549802012-06-01T09:17:47.785-06:002012-06-01T09:17:47.785-06:00The Grzegorczyk Hierarchy:
Starting just with X&l...The Grzegorczyk Hierarchy:<br /><br />Starting just with X<-0 and X <- X+1 and simple nested for loops you can get each level of the Ackermann function. In particular exponential time requires only 2 nested loops.<br /><br />However, the hierarchy DOES show that there is a limit without either recursion or unbounded looping, namely you can't get to non-elementary functions like Ackermann's function itself.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-71677070472688878822012-06-01T07:50:34.934-06:002012-06-01T07:50:34.934-06:00input: n
sum = 1
for i from 1 to n:
sum = 2 *...input: n<br /><br />sum = 1<br />for i from 1 to n:<br /> sum = 2 * sum<br />for i from 1 to sum:<br /> // do stuff<br /><br />// n + 2^n much work has been done.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-11973410985902035422012-06-01T07:35:06.969-06:002012-06-01T07:35:06.969-06:00I'm not sure if there's any relation betwe...I'm not sure if there's any relation between exponential time algorithms and recursion except for the fact that there are some recursive algorithms that take exponential time.<br /><br />For example, the naive algorithm to decide if a number is prime. It iterates over all numbers from 1 to n and checks if they divide n.<br /><br />Along similar lines, any algorithm that iterates over all subsets of a set provided as the input will take exponential time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-64188668570815826292012-06-01T06:40:30.877-06:002012-06-01T06:40:30.877-06:00Give me an array of booleans of length n, and I ca...Give me an array of booleans of length n, and I can simulate counting from 0 to 2^n, and also enumerate the power set of a size n input set. All with two loops and an if. <br /><br />I think this was also the point of the LOOP programming language by Meyer and Ritchie, although they allowed recursion, and so could compute all primitive recursive functions.Peter Boothehttp://imprompt.usnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-13653366920549089392012-06-01T05:33:32.684-06:002012-06-01T05:33:32.684-06:00function(N):
for i from 1 to exp(N)
do something...function(N):<br />for i from 1 to exp(N)<br /> do something constantMatthias GallĂ©http://www.cs.famaf.unc.edu.ar/~galle/noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-60772301543045082622012-06-01T05:12:36.891-06:002012-06-01T05:12:36.891-06:00The language BlooP (Hofstadter) is a language that...The language BlooP (Hofstadter) is a language that captures all primitive recursive sets (a proper subset of the recursive sets) without using recursion.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-89294257603936065512012-06-01T04:07:13.307-06:002012-06-01T04:07:13.307-06:00Dynamic programming is an important technique in e...Dynamic programming is an important technique in exponential time algorithms. You might argue this actually involves recursion. But while the proof of correctness usually does involve induction, the reasonable implementation is often to iteratively fill a table.Thamashttps://www.blogger.com/profile/17766605868066955395noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-63126740892978697062012-06-01T04:01:36.246-06:002012-06-01T04:01:36.246-06:00I guess you may have intended to ask for "san...I guess you may have intended to ask for "sane" computing models, but I get two associations to esoteric languages.<br /><br />First, I wonder what the longest-running non-infinite n-step program in <a href="http://web.archive.org/web/20020425143753/http://www.catseye.mb.ca/esoteric/smetana/index.html" rel="nofollow">SMETANA</a> is.<br /><br />Second, there's <a href="http://web.archive.org/web/20020601134344/http://www.catseye.mb.ca/esoteric/smith/" rel="nofollow">SMITH</a> (a related language), where you have no jumps or other flow control, except to copy selected part of your own program code to some place in front of the program counter. (Turing complete.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-20820480511274674592012-06-01T03:56:58.755-06:002012-06-01T03:56:58.755-06:00Dynamic programming is an important technique in e...Dynamic programming is an important technique in exponential time algorithms. You might argue this actually involves recursion. But while the proof of correctness usually does involve induction, the reasonable implementation is often to iteratively fill a table.Thamashttps://www.blogger.com/profile/17766605868066955395noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-72849623592486500952012-06-01T03:44:58.778-06:002012-06-01T03:44:58.778-06:00Huh? What about the following?
for i = 1 to 2^n: ...Huh? What about the following?<br /><br />for i = 1 to 2^n: print "this is taking a long time'<br /><br />Or, when you forbid "recursion", are you really forbidding looping? (See: http://en.wikipedia.org/wiki/Structured_program_theorem)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-70190955224659465362012-06-01T01:48:57.192-06:002012-06-01T01:48:57.192-06:00ah excellent. Nicely exploits the structure of the...ah excellent. Nicely exploits the structure of the problem to unroll the recursion compactly.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-17787792460704074402012-06-01T01:46:55.388-06:002012-06-01T01:46:55.388-06:00Not even close. The standard iterative algorithm ...Not even close. The standard iterative algorithm for the Tower of Hanoi puzzle takes exponential time.<br /><br />Here's the algorithm:<br />(1) Move the only disk you can that you didn't just move.<br />(2) If the index of the disk is odd, move it clockwise; if it's even, move it counterclockwise.JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-2480338745216403652012-06-01T01:05:38.362-06:002012-06-01T01:05:38.362-06:00Interesting thoughts. I found this blog post, whic...Interesting thoughts. I found <a href="http://blog.rethinkdb.com/high-scalability-sql-and-computational-comple" rel="nofollow">this blog post</a>, which claims "<i>Even if we restrict ourselves to SQL-92, it is possible to write queries of polynomial, or even exponential complexity</i>". Though there is no example query. The interesting point is that SQL-92 is not Turing-complete, but has primitive recursion.qznchttp://qznc.go.tonoreply@blogger.com