Skip to content

About Us

images2

I am Dick Lipton, a Professor of Computer Science at Georgia Tech. I have worked in the area of theory of computation since 1973. I find the whole area exciting and want to share some of that excitement with you. I hope that these blogs inform and entertain you. I hope that you not only learn some new ideas, hear some interesting open problems, but also get some of the history of the area. One of the things I think people sometimes forget is that research is done by people. One of my goals—perhaps the main one—is to get you to be able to see behind the curtain and understand how research works.

I am Ken Regan, also in Computational Complexity Theory at the University at Buffalo (SUNY). I have been delighted to help this blog since mid-2009, and now honored to join the masthead as an author. I have shared the same values and desires as Dick mentions—also attending to the personal side—and have found the partnership congenial as well as collegial.

Pip is both of us, and his story is here.

90 Comments leave one →
  1. Madhu Syamala permalink
    March 3, 2009 2:30 am

    Your posts are just too good. And I like the way you write too. Very hard to find that combination in many tcs blogs. Do keep posting them. Keeps people like me who once had a brief glimpse of tcs want to keep reading.

  2. rjlipton permalink*
    March 4, 2009 9:19 am

    Thanks for your kind comment.

  3. Alex Dainiak permalink
    May 23, 2009 1:55 am

    Your posts are joyful to read. You really can share your excitement with your blog readers, and do it very well. Thank you for your effort!

  4. anon permalink
    May 30, 2009 9:23 pm

    This is truly amazing. Well written, narrative and absolutely delightful. A theory blog, I will surely follow, Professor.

  5. Rafee Kamouna permalink
    June 5, 2009 1:47 pm

    I got addicted to all your blogs. You care for others a lot.

    Best,

    R.K.

    • rjlipton permalink*
      June 5, 2009 2:56 pm

      Thank is one of the nicest comments I can imagine…thank you

      rjlipton

  6. Rafee Kamouna permalink
    June 6, 2009 5:07 am

    I’m just telling the truth at my side which is I get happy when I see your new blogs at the aggregator and I come here to learn more; then it became almost a daily habit.

  7. Ahsanul Haque permalink
    June 6, 2009 4:13 pm

    Awesome!

  8. HappyReader permalink
    June 8, 2009 5:56 am

    I have never seen a blog of such high quality.

    The superb technical quality aside, it is also a pleasure to read
    what has — it appears to me — been written by an absolute gentleman.
    Wonderful. Thank you.

  9. Giorgio Camerani permalink
    June 9, 2009 2:42 am

    My deepest congratulations for your blog, which I find truly interesting and elegant, really well done. I’m consulting it almost every day. I am not aware of any other TCS blog having such a global quality (contents, explanation brightness, real life stories, graphical layout) and being updated with such a high frequency.

    Thanks for your effort, and please keep it on!

    Best regards,

    Giorgio

  10. June 29, 2009 1:28 pm

    Hello,

    This is Armine Hareyan writing from http://www.huliq.com. I visited your blog and liked your content.

    Would you be interested to send us a guest post on any of the issues related to the topics that you cover in your blog. We will publish it in our site http://www.huliq.com

    In return with each guest blog we will give one link in the author’s biline back to your blog. We only ask that the guest post ( we prefer it be a news coverage, sources can be Google News, CNN, MSNBC, Yahoo News, BBC and others) be a unique story and not be published in your blog.

    Please let me know if you may have any questions about http://www.huliq.com.

    If you want to consult the topic with me first that’s perfectly fine as well.

    Many thanks

    Best regards
    Armine Hareyan
    http://www.huliq.com

  11. tcs student permalink
    July 12, 2009 7:47 am

    I love your blog, Prof Lipton. You da man!

  12. John Ryskamp permalink
    September 11, 2009 12:26 pm

    Hello Dick:

    I think you should learn more about the new set theory history. We are right in the middle of a renewed interest in this history. A lot of work is being done, for some reason, in Spain and Mexico.

    Above all read A. Garciadiego, BERTRAND RUSSELL AND THE ORIGINS OF THE SET-THEORETIC ‘PARADOXES.’ I don’t know where he is now. He was at Dibner for a while.

    Godel’s theorems rely on the idea that there is logical content in the paradoxes. If there is NONE, his project is unmotivated.

    And yet the new history shows that he was a very sloppy investigator when it came to finding out whether these “paradoxes” actually possessed logical content, or whether their compulsion was simply an artifact of their rhetoric.

    I think if you read Garciadiego you will see that their compulsion was simply an artifact of their rhetoric.

    Nevertheless, although not only the “paradoxes” had their critics but also, Cantor’s whole set theory notion (see particularly Grattan-Guinness on some of these unsung critics), constructivism forged ahead with new terms of art. Your term “computation” is one of these set theory generated constructivist notions. I think you will wind up concluding that it has no logical content.

    It’s probably expecting too much for you to go back, look at Zeno again, and conclude that the trouble that “paradox” caused Aristotle was no trouble at all.

    However, even the notes editors in the Godel edition often fault Godel’s sloppiness, his lack of inquisitiveness, the unclarity of his ideas. If you look at what Richard said about his own “paradox” (quoted in Garciadiego), you will see how inappropriate it was for Godel to mention this nonsense in his paper. And that is not the only nonsense in Godel’s paper.

    You should ask yourself (and it is the million dollar question with regard to Godel’s theorems):

    where is the constructivist intervention in Godel’s argument?

    That is, where does he make an arbitrary intervention in his logic in order to keep his conclusions from becoming paradoxical? This was the method handed down by the set theorists.

    Einstein, for one, used the method in constructing the relativity of simultaneity. He called his constructivism “practical geometry” and as I say in the last part of the article linked below, he used it to insert an undefined “natural” coincidence into the relativity of simultaneity. As you will see, this causes insurmountable problems for the relativity of simultaneity. I am gratified to see that this has put a monkey wrench in research into relativity.

    I am interested in an identification of Godel’s constructivist intervention in his argument, at the same level of precision.

    Identifying these constructivist interventions has become the project of 21st century inquiry. As you will see from the paper, it is going on with respect to many major ideas, as we boot constructivism out of our discourse. I am especially interested in the progress it is making with respect to both Motoo Kimura and Darwin. You will see the references in the paper.

    Ryskamp, John Henry,Paradox, Natural Mathematics, Relativity and Twentieth-Century Ideas(June 17, 2008). Available at SSRN: http://ssrn.com/abstract=897085

  13. Alan Turing permalink
    September 15, 2009 1:40 pm

    Keep it up. Great post today!

  14. September 26, 2009 7:19 am

    I’ve been watching Star Trek since I was 6 years old and love science fiction.

  15. ILIA TOLI permalink
    September 27, 2009 12:24 am

    I believe that P = NP. I wouldn’t bet a dollar though. It’s true and might take more than 1 lifetime to prove. Given the relevance…
    Well, I’m working on it. Not that this is a scary news but it’s tons of fun.

  16. Donald B permalink
    September 28, 2009 6:44 pm

    Congrats on your link from Harper’s (http://www.harpers.org/#hbc-90005787)! (Though they likely intend irony, I enjoyed your post.)

  17. raphael permalink
    September 29, 2009 9:35 am

    thanks for your intellectual sharing, i enjoyed the reading very much indeed.

  18. Nick permalink
    October 1, 2009 10:27 pm

    This page is a blast, I really appreciate what you are doing here. Too often it seems that the excitement of academia is locked behind the walls of pay journals and jargon.

  19. November 22, 2009 5:18 pm

    Great blog. I would have bee searching for a long time a web site like this. Thank you

  20. January 8, 2010 9:57 pm

    Thank you so much for running this blog.

    I don’t deeply grok most of the topics you write on. But it opens a window into fascinating new territory that I occasionally venture into and derive a lot of learning and joy from.

    It inspires me to see someone putting so much effort and producing quality work when there is no obvious economic incentive.

  21. January 23, 2010 2:43 pm

    This had been one of my favorite blogs for a while. Much of it is difficult reading for me (parts are just plain over my head), but it’s fascinating stuff and for clear, genial presentation it’s a model.

    And then I realized: you’re the professor who taught me Theory of Computation back at Yale around 1977. It finally connected when you mentioned working with David Dobkin.

  22. February 26, 2010 1:00 pm

    Congratulations for the excellent blog. It is definitely one of my favorites. The areas of complexity and algorithms are fascinating and your blog emphasizes the beauty that they entails. Right now I’m attending Prof. Karp’s class in combinatorial algorithms and data structures. Thus, reading your blog is for me a mixture of pleasure and study. Thank you.

    Best wishes,

    Elói Pereira
    PhD Student
    Systems Engineering, CEE
    UC Berkeley

    • rjlipton permalink*
      February 26, 2010 5:35 pm

      Thanks very much. Must be great to be in Karp’s class.

  23. March 10, 2010 6:47 pm

    Love your fascinating blog. Wrote a post today to recommend it. Thank you very much.

  24. April 7, 2010 6:29 pm

    Hear hear! This is really a great blog. You tend to bring across many important and technical things in a very lucid and attractive way, and with nice personal stories: a lot of fun to read. I was warned about your blog by couple of your students: Atish and Danupon, and sure enough, it is addictive!

  25. April 14, 2010 8:14 pm

    I learnt computation complexity by reading books only, and I don’t have a solid background in this area. But I am quite interested in the problem and NP=P, and I am so glad to find your blog which is dedicated to the problem.

    I have written an article about permanent, Calculation of Permanent with new method (with complexity the same as the Ryser’s formula). I know this is not a very useful method, but I just would like to know if the article and the claim, with complexity the same as the Ryser’s formula, is indeed correct. If you can have a look and give me a some comments, it would be very great. Thank you.

  26. Linfeng Liu permalink
    July 11, 2010 9:08 am

    I’m very happy to see much more helpful articles here.

  27. Jürgen Geuter permalink
    August 10, 2010 3:14 pm

    Dear Mr. Lipton.

    Considering the recent uproar about the P \neq NP proof I thought it would help many people to get an understandable explanation of what P and NP actually mean. Since I do a podcast about some scientific and social topics I thought it might be interesting to get an expert to try to communicate to “normal” people what all the fuss is about.

    Looking at your writing I think you’d be perfect for this task, sadly I couldn’t find an email address here to talk to you directly, so I’ll try it this way.

    If you might find the time to talk to me (via Skype or something similar) about P and NP please drop me an email to jgeuter(at)monkeycode.org. Thanks!

  28. August 12, 2010 5:53 am

    Thank you for your blog, very informative and engaging!

  29. Lizhi Du permalink
    August 13, 2010 2:17 am

    Dear Professor Dick Lipton:
    I know that you are a great specialist in theoretical computer science。I have a procedure hp4.exe (in VC++,my many years job), which can calculate Hamilton Path from vertex 0 to vertex n-1 for any kind of undirected graphs, very quick, smooth, I have calculated almost 1 billion inputs, no fail. If you have interest, I can mail hp4.exe to you immediately. Only after you run the hp4.exe, then you can trust me. Then, we can exchange ideas!
    I appreciate you if you can agree.
    sincerely yours,
    Lizhi Du
    I am an associate professor in China, my email: edw95@yahoo.com

    • Anonymous permalink
      August 15, 2010 1:48 am

      Lizhi Du:

      LOL. Nice attempt at getting a trojan on Lipton’s box.

  30. August 15, 2010 5:03 am

    Your blog is definitely among the top sites on computational complexity &etc. I would rate it among Scott Aranson’s and Lance Fortnow’s blogs’ league… These few websites have piqued my interest in the field and hope they continue to do so.

    Your article on Deolikar’s proof was quite informative… Unlike newspaper reports of it being solved!!!

    Best wishes
    Shabbeer Hassan,
    Bangalore,
    India.

  31. August 18, 2010 8:44 am

    Dear Prof Lipton:

    first of all, thanks for your blog which I enjoy reading on a regular
    basis. – I decided to start my own blog called “Order, topology, and other
    basics” in which I want to write musings on topics of point-set
    topology and order theory.

    I took your blog on my blogroll and want to ask you if you could take
    me on yours? That would be very kind.

    Many thanks,
    Dominic

    PS: sorry for posting this here, in what seemed like a fit of Google illiteracy, I was unable to find your e-mail address.

  32. August 20, 2010 9:25 pm

    Dear Professor Lipton:
    I know that you are a great and busy scientist。I have a procedure hp4.exe (in VC++), which can calculate Hamilton Path from vertex 0 to vertex n-1 for any kind of undirected graphs, very quick, smooth, I have calculated almost 1 billion inputs, no fail. Now, I want to mail hp4.exe to you . Only after you run the hp4.exe, then you can trust me. Then, we can exchange ideas!

    I know you are busy, you only need to let one of your students to do it!

    This procedure can calculate Hamilton Path in polynomial time for all kinds of undirected graphs, no matter how dense they are or how sparse they are or how uneven their edges’ distribution is. Utterly correct and quick, no exception.

    This procedure works very smooth for all kinds of undirected graphs, i.e., for graphs with the same number of vertices, except for a little trivial instances which are very easy to calculate, their running time are very close to one another. So using my procedure, there is no graph to cost much more time than others, i.e., there is no “dead angle” for my procedure.

    I assert: my procedure hp4.exe is the best one, the excellent one, the wonderful one. No other procedure for finding Hamilton path can be as good as my hp4.exe in all of this world!

    Sincerely yours,
    Lizhi Du
    College of Computer Science and Technology,
    Wuhan University of Science and Technology, Wuhan 430081, P.R. of China
    Tel: 86 13554171855
    My email: edw95@yahoo.com

    Again I know you are busy, you only need to let one of your students to do it!

  33. August 22, 2010 9:41 am

    Your site has allowed me to look in another way at many things. Thanks, Dick!

  34. Mario permalink
    November 4, 2010 6:11 am

    Hello,
    Your RSS feeds do not work (the last update is galactic algorithm), i missed three updated due to that… :)

    Thanks alot and thanks for that great blog!!!!!

    • Ørjan Johansen permalink
      November 4, 2010 10:43 pm

      They work for me (main one and comments, although the latter sometimes misses comments due to a 10 item cutoff). I often force update my RSS’s rather than wait for the schedule though.

      • Mario permalink
        November 6, 2010 12:44 pm

        You are right, the rss works – just my foxi did not update them ;)

      • Ørjan Johansen permalink
        January 14, 2011 12:27 am

        Like I mentioned in November, the comment RSS feed keeps on occasionally losing comments due to this 10 item cutoff. However I have the impression it’s rarely missing by much. I don’t know how this really works, but is there any chance you could increase it to 20 or so?

  35. November 7, 2010 1:22 pm

    Thank you for the most excellent mathematical blogging!

  36. PHILIP BAUTER permalink
    November 12, 2010 3:47 pm

    I knew Zeke Zalcstien in the late 70′s and early 80′s. If you could let him know I would like to say hi, I’d appreciate it. I haven’t been in contact since then. I’d tell him “It is around the corner.” He’ll know what I mean. We were both getting deep into nutrition.

    Thanks.
    P.Bauter, pbauter@net66.com

  37. A Fan permalink
    November 16, 2010 11:58 pm

    Georgia Tech doesn’t pay enough:

    Dick, this blog is an outstanding resource. Thanks. One quibble. How disappointing that it includes advertisements. For example, almost all the others on your blog roll choose not to. While I don’t want to begrudge you the extra income for the undoubted extra effort required to put it together, I just want you to know that it does spoil the enjoyment of reading it just a little.

    Denise

    • rjlipton permalink*
      November 17, 2010 8:29 am

      A Fan

      I can turn them off by upgrading etc. Will consider doing that.

  38. November 30, 2010 1:06 pm

    love the site. You might find my youtube video on Georg Cantor interesting because it overlaps your posts on Turing, Godel, et al. a little:

    the video is on the deeper philosophy of Georg Cantor: http://www.youtube.com/watch?v=_Ds6XtElf3E check it out in HD. I’d love to know what you think, Professor.

  39. Joe permalink
    January 9, 2011 11:58 am

    I’ve been a reader here for a good while now. Big fan, too. It’s a great place to hang out. I haven’t come across any contact information anywhere though, so I’ll just put this here instead. I apologize that by doing this ahead of time, since it has the unfortunate effect of spamming the about page with an external link. I think you’ll see it’s potential though.

    I just stumbled across Stack Exchange’s Theoretical Computer Science forum (in beta). It’s something I feel has the potential to be a very useful place to ask such questions. And by reading your stuff here, I know you and those who help you could help bring it to life. Akin to Jon Skeet’s ability to answer almost any C# question on Stack Overflow. This is the site: http://cstheory.stackexchange.com

    If you’ve never heard of Stack Exchange, check out http://www.stackoverflow.com to see one of their sites in action. This example in particular is a wonderful resource for programmers. I’d love to see an equally good place for CS theory. So check it out if you have the time. At the time of writing this, there’s a popular question on where people should go for help on their research and publishing. So these kinds of questions and answers can help out so many students involved in theory in a very practical way.

  40. Eddie permalink
    January 23, 2011 9:52 am

    http://romvf.wordpress.com/2011/01/19/open-letter/

    Would love to hear your comment on this. :)

  41. February 24, 2011 8:05 pm

    Nice blog Prof.Lipton. it will be my pleasure to start following this blog..!!!

    –U.

  42. Tupac Shakur permalink
    March 24, 2011 5:26 pm

    You are cooler than every rapper I know.

    Your post on Ed Clarke’s approach was a nice read.

    I hated TOC in college. Age has tempered my juvenile perceptions on the most fundamental faculty of computer science.

  43. May 21, 2011 9:39 am

    I saw that chess program in 1972 – it was one of the best things I ever saw on tv. And so simple!

    • August 30, 2012 9:17 am

      I remember back then in 1999, a dos chess game. The computer was so hard to defeat. Do you think which is better, computer or the game creator? can computer defeat the game creator?

  44. June 24, 2011 8:07 pm

    Very good blog. I like reading posts.

    Have a look a my blog at http://mathematicsbhilai.blogspot.com/

  45. September 13, 2011 5:15 am

    Dear Prof. Richard J. Lipton,

    What will be the effect of deciding complexity of the Problem of Isomorphism of Graphs on problem of deciding P = NP (or, P != NP) ? Where do you expect this problem will go (i.e. in P category or NP Complete category)?

    Best Regards,

    Dhananjay P. Mehendale

    • DPM permalink
      May 23, 2013 2:04 am

      There will be no effect of deciding complexity of problem of “Isomorphism of Graphs” on problem of deciding P = NP (or, P != NP) as this problem doesn’t belong to set of NP complete problems. Thanks.

  46. October 23, 2011 11:47 am

    If you believe in Cantor, what is your answer to the following questions?

    Consider a sequence of sets with increasing cardinality:
    o
    oo
    ooo

    Enumerate the elements of the sets
    1
    1,2
    1,2,3

    Is there a limit set, omega say?

    Enumerate the elements of the sets
    1
    2,3
    4,5,6

    Is there a limit set, the empty set say?

    Enumerate the elements by superscripts like in the first case and by subscripts like in the second case.

    Is there a limit set? What kind of set is it?

    Regards, WM

  47. November 25, 2011 5:56 pm

    Dear Dick Lipton, I would like to thank you for your research and for sharing your views and ideas. I came across your blog just two days ago and have spent the past two days trying to formulate a “cultural project” which presents research as art. I am a student of a MA in Cultural Production program at the University of Salzburg and I also compose electronic music using the computer as my instrument and “field” recordings as many of my sounds. This project I am dreaming up would involve using some of your ideas and research as tools for addressing problems in society. The research I would do based on your post on Erdös and the Quantum Method would be presented as non-text archival audio samples (placed on a online archive for people to download and use for free) along with musical interpretations of the results (This would be sampling research for artistic expression as an experiment). I am deeply interested in collaborating with you in some way. Please let me know what you think! I want to make this project happen. :))
    ps. what is the best way to establish communication with you?

    • November 25, 2011 6:18 pm

      oh! i forgot to mention, i failed college algebra 3 times before I finally passed the course on the 4th try. i would have never imagined i would use math and quantum theory methods as metaphors for society and as proposals for creating awareness of a civil society. however, at some point, i began “doing the math”, and recently referring to humans as homogeneous polynomials: finite with variables and constants; operate through addition, subtraction, multiplication (and division as a metaphor for problems in society). i realized we are walking math and therefore walking possibilities, and positive/ progressive possibilities for that matter. seeing potential for an active socially conscious civil society is what drives me to do this project; connecting these ideas to composition methods of electronic music using the computer as an instrument is my intuitive creative expression and need.

      both/and statements: this is art with a cause. “causes” create art.
      (reflections on the purpose of art)

      thanks again for your time.

  48. Ørjan Johansen permalink
    November 30, 2011 3:55 am

    Regarding the RSS comment feed 10 post cutoff problem which I’ve mentioned above, as well as in another post. (I feel like I’m nagging, but on the other hand no one’s ever responded.) Apparently this is a known problem

    The solution for WordPress seems to be to ‘Amend “Syndication feeds show the most recent” in Admin/Settings/Reading.’

    Could someone please increase this to something more reasonable for the current comment volume? I checked the feed just before turning off my laptop last night, and when I just got up I was happy to see there were only 8 new comments so I could see them all in the feed…

    • Ørjan Johansen permalink
      December 2, 2011 10:11 am

      I cannot resist posting again about this silly feed business: Strangely that message hasn’t showed up in my feed, despite it being relatively quiet in the intervening time. I wonder if it has something to do with being held up in the spam filter (I put a little too many links in it). So I cannot help but hypothesize an explanation: The feed shows the latest comments by posted date instead of by when they actually show up publicly, meaning that if more than 10 other posts are made before it gets out of the spam filter, it will not appear in the feed at all, no matter how often it is checked.
      (Now waiting for it to suddenly appear in my feed anyhow, voiding my hypothesis. :P )

      • Serge permalink
        December 2, 2011 11:16 am

        Maybe you should consider reading this blog on the web… :)

      • Ørjan Johansen permalink
        December 2, 2011 3:39 pm

        Oh, I am reading this blog on the web. I am talking about the comments, not the main posts themselves, which don’t come anywhere near often enough to trigger the cutoff, and which besides are listed sorted in the archive so I could find them even if it happened.

        Without the RSS comment feed (or the blog comment list on the right side, which seems to also be just 10 comments, although I am almost sure I saw it increasing briefly during the Deolalikar discussions) I don’t know any reasonable way of knowing whether there are new comments. Even checking recent posts by hand doesn’t work for new comments to really old posts.

      • Serge permalink
        December 2, 2011 4:50 pm

        Actually I did mean the comments, not the posts. There’s a possible confusion because you can say “to post a comment” and as a francophone I’m not aware of the usage. I think a comment limit of 20 to 25 would do better. It would prevent us from missing sporadic comments on old posts. Comments on new posts are less likely to be missed since we can always use ctrl-F to search the page for the current date. :)

      • Ørjan Johansen permalink
        January 18, 2012 9:00 pm

        Sigh, it has been silent lately, but there it starts overflowing again, like whenever a troll and a crank feeds off each other… sorry for the grumpiness.

    • Ørjan Johansen permalink
      January 20, 2012 1:56 am

      Since I have heard no comment from either Prof. Lipton or Regan, not even to say they do not wish to do this, I wonder if I have failed to make it clear – the above suggestion if it is to be done must be applied by the blog authors, it cannot as far as I know be achieved by the readers.

  49. January 21, 2012 10:52 pm

    Dick, I don’t know if I ever told you this. But every conversation I’ve ever had with you has been a privilege and a pleasure. Your mental energy and enthusiasm is exhilarating, inspiring and staggering. My brief time with the more theoretical aspects of computing was long ago but I truly enjoy those patterns of thoughts, even though I spend most of my time on practical aspects of how to build better siftware, cheaper. Thanks for this blog. It is like I get to have a conversation with you anytime.

    Keep on thinking!
    Jeff

  50. January 31, 2012 3:49 pm

    It is a very nice website you have here. I will return!

    A couple of years ago, I wrote a “paradox”, that you might find interesting. Have a look: http://blogoff.simonjensen.com/#post4

    A friend of mine recommended your site, and asked me to ask for your opinion. Hope yo can spare a moment.

    Best regards,
    Simon Jensen

  51. Ørjan Johansen permalink
    February 12, 2012 1:15 am

    And there I go again, opening tabs with all recent posts to find all the interesting comments which get lost beyond the cutoff limit I’ve nagged about before above. (It’s beginning to look like all I say here, isn’t it.) Except of course I have no idea how to find the ones in non-recent posts.

    (The comment sidebar limit increasing to 15 recently has helped a bit, but now that got overflowed too… the RSS limit seems still to be 10.)

    • Ørjan Johansen permalink
      February 13, 2012 6:20 am

      Never mind, I just unsubscribed instead.

  52. April 16, 2012 6:40 am

    This blog is just COOOOOOOLLLLLLLLLLLLLLL. Please, keep it alive!

  53. arunaugustine permalink
    May 22, 2012 5:30 pm

    Dear Pip,

    I recently stumbled upon and became curious about the P=NP problem. The stumbling occurred when I took a seminar course in the neighboring arts and technology department along with an advanced algorithms class in my CS department. And the muses were kind enough to give me some ideas for my seminar report titled: “Schrodinger’s Cat in flatland”. Although trembling with fear at the idea of presenting such a first cut work as this to an expert such as you, may I ask for a few minutes of your precious time to read and comment on this document?

    It is available here: https://docs.google.com/document/d/1JV0Ey3wY71x2RqFP5wIRcTtyo9QPzZzq_GuB_txax5E/edit

    Sincerely,

    Arun

  54. arunaugustine permalink
    May 22, 2012 5:34 pm

    great blog!

  55. November 22, 2012 7:56 am

    This is the best idea about integer factorization, written here is to let more people know and participate.
    A New Way of the integer factorization
    1+2+3+4+……+k=Ny,(k<N/2),"k" and "y" are unknown integer,"N" is known integer.
    True gold fears fire, you can test 1+2+3+…+k=Ny(k<N/2).
    How do I know "k" and "y"?
    "P" is a factor of "N",GCD(k,N)=P.

    Two Special Presentation:
    N=5287
    1+2+3+…k=Ny
    Using the dichotomy
    1+2+3+…k=Nrm
    "r" are parameter(1;1.25;1.5;1.75;2;2.25;2.5;2.75;3;3.25;3.5;3.75)
    "m" is Square
    (K^2+k)/(2*4)=5287*1.75 k=271.5629(Error)
    (K^2+k)/(2*16)=5287*1.75 k=543.6252(Error)
    (K^2+k)/(2*64)=5287*1.75 k=1087.7500(Error)
    (K^2+k)/(2*256)=5287*1.75 k=2176(OK)
    K=2176,y=448
    GCD(2176,5287)=17
    5287=17*311

    N=13717421
    1+2+3+…+k=13717421y
    K=4689099,y=801450
    GCD(4689099,13717421)=3803
    13717421=3803*3607

    The idea may be a more simple way faster than Fermat's factorization method(x^2-N=y^2)!
    True gold fears fire, you can test 1+2+3+…+k=Ny(k<N/2).
    More details of the process in my G+ and BLOG.

    My G+ :https://plus.google.com/u/0/108286853661218386235/posts
    My BLOG:http://hi.baidu.com/s_wanfu/item/00cd4d3c5a2fd089f5e4ad0a

  56. shane permalink
    May 1, 2013 4:00 pm

    Sir, where might I find a blog or accessible book on discriminants? I want read up a little bit more before I teach my kid how to solve quadratics. I am trying to find material that puts HS school algebra into a little more perspective by taking a tid-bit and running with it a little bit. Best regards on a fine blog. Shane

  57. ooten permalink
    June 17, 2013 1:34 pm

    Hello,
    I don’t understand why you’re using https protcol to publish the blog. Thanks for it.

  58. September 13, 2013 3:24 pm

    Way cool! Some extremely valid points! I appreciate you
    writing this article plus the rest of the website is extremely
    good.

  59. November 8, 2013 12:01 pm

    Hello Dr. Lipton,

    I am currently running a crowd funding campaign for my upcoming educational game Sweet Math. I was wondering what is the process to get a story out on your blog.

    Here’s more information about the game itself: http://www.kickstarter.com/projects/89952638/sweet-math

    For those of you who think education is a key to make the world a better place check out our educational game Sweet Math. We are currently at 69% of our funding goal and the campaign will end on November 14th. We accept donation for as low as $1. http://www.kickstarter.com/projects/89952638/sweet-math

    The game let player practice arithmetics with their entire family.

  60. January 2, 2014 10:19 pm

    I wanted to make a suggestion on a topic. This was the first synthesized music created by Wendy Carlos in the 70′s. I once built my own moog synthesizer out of amp chips, creating seven adjustable oscillators whose sub tone volume could be adjusted. I was going to use Flip Flops to jump octaves. Instead I started hanging out in a friends band that had the real thing.

    http://wintersbutterfly.com/2014/01/02/switched-on-bach/

  61. Dustin Yoder permalink
    May 5, 2014 12:12 am

    I have been working on a chess database structure that is useful for solving chess as it can be pruned to only store winning moves but will still allow fast access to positions and can keep track of losing paths of play without storing every losing position. I’d like to get a real credible person’s take on this approach. Would you be willing to discuss it with me?

  62. May 30, 2014 10:52 pm

    Somewhat off the topic, but I am at my wit’s end looking for an answer to a problem that has been bugging me for over 6 years. I am a computer scientist with an extensive math background, even having taken a course on computability with Martin Davis at NYU. So it bothered me when I was reading a novel that referred to Chaitin’s constant, and I had never heard of it. Since then, my interest in such things has been rekindled. My problem is, I’ll be d***ed if I can remember the name of the book. It was sort of a techno-thriller, and Chaitin’s constant was sort of a key to get into something. Can you or your readers help me with this. Oh, and BTW – great blog!!

  63. June 25, 2014 6:15 pm

    Dear Prof. Lipton, thank you for sustaining this daringly intellectual blog! I have a philosophical math question which I wanted to ask here, if I may. Here goes:

    Math is a system of knowledge that is unambiguously stored within an
    “accounting” language which underlies all work ever written on the subject,
    regardless of its form (symbolic, English, hybrid, etc).
    The uniqueness of this underlying formal language is manifested in
    the consensus amongst scientists when they go about their daily
    communications.

    That language is—by choice or necessity or taste, but certainly by agreement—acyclic:
    It begins with axioms (of Set Theory) and grows with operations (of Formal Logic).

    Acyclic graphs (equivalently formal systems) are not the only ones we know.
    Systems of truth can be circular—as if suspended in air without axioms—and
    their sophistication can be accomplished by refinement as opposed to growth.
    This is what we call CSP problems in Computer Science.

    Why is that we study formal systems with no beginning or end (CSP problems
    in combinatorial optimization), but we use a language to describe
    our findings (Formal Logic) which is an acyclic infinite system?

    This question rings familiar when you put it in the context of two painful paradoxes
    in math: the search for correlation-cause-effect resolution and the question of existence
    of one-way functions.

    Could it be that our choice to use an axiomatic language to talk about math
    is creating singularities: one at the place when information comes into
    math (the act of observation) and at the other end of the math universe
    (the term for the “unknown” in math as language—randomness).

    Could the resolution of both paradoxes simply be to rethink the
    language of mathematical expression so that those two open questions
    are collapsed into one and converted into a theorem—thereby going
    from two conundrums to one result, or (-1) + (-1) = +1.

    Here’s where this problem emerges in practice:

    I find it odd that experimental sciences (when they are correct) report:
    “The observations show a correlation between … and we are going
    to use some side theory to disambiguate between cause-and-effect.”
    What side theory?

    The very side theory they are appealing to is Math and Math resolves their
    meaningless and inane (due to cognitive bias and short historic memory)
    question (of “Is correlation cause or effect?”) into another
    meaningless one, which is the collection of paradoxes intrinsic in
    Math—the provider of the answer—as an axiomatic language.

    But if Math wasn’t serving to the asking experimentalist and rather aiming
    to build a language that explains everything as seen and observed and testified to
    by its users (people), in a consistent impartial and non-arguable manner, it would have
    to offer a new tool to record and reason about correlation without breaking it
    into cause and effect. No?

    Thank you so much,
    Petar

    • June 26, 2014 12:21 pm

      I would like to add a further refinement of my question, to make the problem even more visible:

      The issue is that when Mathematician think about math they find the notion of “double-checking” everything from axioms to present interests inhumanly difficult: and it is. But this is the wrong place to look.

      That path (axioms to modern interests) is the path of history. But the path through which Math is understood by a person (the consumer of it) is not historic, rather it is through their mother tongue (whatever it may be) which as Chomsky tells us is a cyclic infinite formal system. Not acyclic.

      That’s all there is to it.

      Because Math doesn’t care to check back and “defragment”, it is sticking to this acyclic system of axioms+logic which is simply—ironically in math’s own terms—a local view on a large manifold (the formal system of truth), which is slightly incorrect at the fringes, the way a tangent space is not accurate away from the focus. And these inaccuracies manifest themselves into ever more tightly phrased problems of the Clay Math Institute.

      They are Math language closing in on its own contradiction. Beautifully,
      the process of abstracting a few very hard open problems is—surprise—Occam’s razor in reverse (for physicists, this is “unification in reverse”).

      I think the picture is simple.

      • June 26, 2014 10:17 pm

        To put it yet differently: How come no one ever asks why Turing presumed that a machine has input and output? If the idea is that his machine models the physical universe, then what is the I/O a metaphor for? This is a cognitive slip up, because we all tend to see (and think) of objects as modular and “in front of us”, but the world is all around and a model of it will not have an input and an output. It would be a closed system.

        Closed systems are symmetric objects, by definition. Input/output devices are not. They are the epitome of directionality. Isn’t that puzzling?

        Math has already tinkered with this insight in the form of Choiceless Polynomial Time. But it doesn’t seem to have been used for the right question.

Trackbacks

  1. The most important Theoretical Computer Science problem is inconsequential
  2. Da blogosfera: a carta recente de Alexandre Grothendieck « problemas | teoremas
  3. P ≠ NP ? [ Vinay Deolalikar from HP Labs Publishes His Proof to the Web, $1Million Clay Institute Prize May Very Well Await ] | Computational Legal Studies™
  4. One Heckler and My Answer | Sun Ju's Blog
  5. Are MOOC Students Cheating Or Mastering the Material? « Gödel’s Lost Letter and P=NP « Computing Education Blog
  6. Обработка ошибок и безопасные состояния в программировании | Yasik.org
  7. Blog Free or Die « Pink Iguana
  8. Bounded rationality: systematic mistakes and conflicting agents of mind | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,537 other followers

%d bloggers like this: