Skip to content

A Course on Complexity Theory

January 12, 2010
tags: , , , , , , , , , , , , , ,


What should a course on complexity theory cover?

Alan Cobham is a famous theorist who was a theorist before there was theory. Does that make sense? He is usually credited, along with Jack Edmonds, for creating the most important complexity class—polynomial time. The picture is of Jack, not Alan: there seems to be no picture available of Cobham.

Today I plan to discuss what I should teach in my spring complexity theory class. I would like your input. I will of course teach what polynomial time is.

Alan Cobham’s 1965 paper entitled “The intrinsic computational difficulty of functions” is usually viewed as the first definition of {\mathsf{P}}. It was one of the first papers to discuss complexity theory.

There were other people on the trail of {\mathsf{P}}; for example, the great number theorist, Derrick Lehmer, wrote a paper called, “The Economics of Number Theoretic Computation,” which is in the proceedings of a conference held at Oxford in August 1969. He calls “subroutines” of logarithmic order if they use operations that grow with the logarithm of the size of the numbers. In his model the greatest common divisor of two integers {0 < x < y} is logarithmic: he cites Gabriel Lamé who in 1844, showed that Euclid’s algorithm requires at most 5 times the number of decimal digits of {y} of divisions. Thus, he counts basic arithmetic operations as unit cost.

As for Cobham, my best and most mysterious story concerns the time I first taught complexity theory at Yale. It has nothing to do with polynomial time.

I was planning on presenting a theorem due to Cobham on the time required to determine whether a number is a perfect square. He had proved a nice non-linear lower bound for one-tape Turing Machines—such bounds are only possible on such machines. But, as I read the version of his proof from a survey paper, in order to prepare my lecture, I realized there was a “bug”—the proof was incorrect.

I tried to fix the bug, but could not see how to do that. Cobham was famous, surely his theorem was correct. So I decided to go to the source and read his original proof. This was the early 1970’s and there was, of course, no Internet, no e-mail, no mathematics databases. The only way to look up information was at the library. So off I went to Yale’s great engineering library, found the thick bound journal where Cobham’s article was located, and turned to right page. There at the page was nothing. Nothing. The whole article had been razor-cut out of the journal. It was gone.

It’s awful that people deface library books, but I assumed it had happened because the article was so famous. So I called my good friend and colleague Rich DeMillo, who at the time was faculty at another university. He agreed that he would go directly to his library and get a copy that afternoon.

Later that day I got a call from Rich. He too had looked up Cobham’s arcticle and there in the journal was nothing. Nothing. Someone had also razor cut out that copy of the Cobham article.

We were both shocked. How could two copies, of the same article, at different libraries, both be missing? It seemed strange. I immediately had a crazy thought: what if Cobham’s theorem was wrong? Could he—or someone else—be going around the country removing every copy of the incorrect paper? No. That was way too crazy, but it did occur to me.

In any event, I had to present the paper. So I sat down and eventually worked out a correct proof, which I later presented to my class. I did weeks later find a copy of Cobham’s article. It had a correct proof, the same proof that I figured out. There was no secret society removing journal articles—just a strange coincidence. Oh well.

Let’s now turn to an attempt to list what my students will need to know.

Should They Know That?

I am teaching graduate complexity theory this spring, and I have some ideas on how to structure the class in a different way than usual. For starters I want to list what the students should know. I want them to know certain material “cold.” I want them to know, for example, the exact definition of the complexity class {\mathsf{BPP}}, know the statement of Toda’s Theorem, and know the proof of Savitch’s Theorem.

I am planning to de-emphasize the requirement that they can problem solve, and produce solutions to new questions in complexity theory. Over the years I have discovered that many students have trouble solving creative problems, since they differ greatly in their problem solving abilities. I do expect, in this class, that every student will know the basic definitions, results, and some of the proofs of the field. Knowing this material may not be sufficient to be able to do creative work in complexity theory, but it certainly is necessary. If you do not know what {\mathsf{NL}} is, then you certainly cannot solve some question such as improve Savitch’s Theorem. But, more importantly, if they know this basic material they will know what complexity theory is all about. This is the main goal of the class.

Definitions That Are Important

You will need to know the following definitions:

  1. What is a boolean string?
  2. What is a problem—in the formal sense?
  3. What is a Turing Machine?
  4. What does it mean for a Turing Machine to solve a problem?
  5. What are the following basic complexity classes:
    1. {\mathsf{P}}
    2. {\mathsf{NP}}
    3. co-{\mathsf{NP}}
    4. {\mathsf{L}}
    5. {\mathsf{NL}}
    6. {\mathsf{PSPACE}}
  6. What does it mean for a complexity class to be closed under the following operations?
    1. Union
    2. Intersection
    3. Complement
  7. What is a Turing reduction?
  8. What is a logspace reduction?
  9. What is a complete problem?
  10. What is an {\mathsf{NP}} complete problem?
  11. What is an {\mathsf{NP}} hard problem?
  12. What are the following problems?
    1. What is the SAT problem?
    2. What is the Clique problem?
    3. What is the TAUTOLOGY problem?
    4. What is the Knapsack problem?
    5. What is the Factoring problem?
    6. What is the Graph Isomorphism problem?
  13. What is a boolean function?
  14. What is the circuit complexity of a boolean function?
  15. What is the formula complexity of a boolean function?
  16. What is the {AC^{0}} complexity of a boolean function?
  17. What is an oblivious Turing Machine?
  18. What is {\mathsf{BPP}}?
  19. What is {\mathsf{RP}}?
  20. What is {\mathsf{PP}}?
  21. What is {\mathsf{PH}}?
    1. What is {\Sigma_{1}^{p}}?
    2. What is {\Pi_{1}^{p}}?
    3. What is {\Sigma_{k}^{p}}?
    4. What is {\Pi_{k}^{p}}?
  22. What is {\mathsf{P}/f(n)}?
  23. What is {\mathsf{P/poly}}?
  24. What is {\mathsf{EXP}}?
  25. What is {\mathsf{NEXP}}?
  26. What is {\mathsf{AM}}?
  27. What is {\mathsf{\#P}}?
  28. What is {\mathsf{IP}}?
  29. What is {\mathsf{BQP}}?

Results That Are Important

For these results you will need to know their precise statements.

  1. Hierarchy Theorem for {\mathsf{DTIME}}.
  2. Hierarchy Theorem for {\mathsf{DSPACE}}.
  3. Hierarchy Theorem for {\mathsf{NTIME}}.
  4. Cook’s Theorem.
  5. Savitch’s Theorem.
  6. NLOG closed under complement.
  7. Shannon: existence of hard boolean functions.
  8. Fischer-Pippenger Theorem.
  9. Kannan Theorem: {\mathsf{PH}} has problems which require large circuits.
  10. Karp-Lipton Theorem.
  11. Non-Graph Isomorphism is in {\mathsf{AM}}.
  12. Sipser: {\mathsf{BPP}} in polynomial hierarchy.
  13. Baker-Gill-Solovay Oracle Theorems.
  14. Levin’s Theorem.
  15. Parity is not in {AC^{0}}.
  16. {\mathsf{PCP}} Theorem.
  17. Toda’s Theorem.
  18. Nisan’s Theorem on de-randomization of space computation
  19. The known relationships among the following classes:
    1. {\mathsf{P}}
    2. {\mathsf{NP}}
    3. co-{\mathsf{NP}}
    4. {\mathsf{L}}
    5. {\mathsf{NL}}
    6. co-{\mathsf{NL}}
    7. {\mathsf{BPP}}
    8. {\mathsf{AM}}
    9. {\mathsf{IP}}
    10. {\mathsf{\#P}}
    11. {\mathsf{BQP}}
    12. {\mathsf{PSPACE}}

Thus, you will understand this figure and more:

Proofs That Are Important

For these results you will need to know their proofs in detail.

  1. {\mathsf{NTIME}[t] \subseteq \mathsf{DSPACE}[t]}.
  2. {\mathsf{NSPACE}[t] \subseteq \mathsf{DTIME}[2^{O(t)}]}.
  3. Hierarchy Theorem for {\mathsf{DTIME}}.
  4. Hierarchy Theorem for {\mathsf{DSPACE}}.
  5. Cook’s Theorem.
  6. Savitch’s Theorem.
  7. {\mathsf{NLOG}} closed under complement.
  8. Shannon: existence of hard boolean functions.
  9. Kannan Theorem: {\mathsf{PH}} has problems which require large circuits.
  10. Karp-Lipton Theorem.
  11. Non-Graph Isomorphism is in {\mathsf{AM}}.
  12. Sipser’s Theorem that {\mathsf{BPP}} in polynomial hierarchy.

Open Problems

What have I left out? What should I leave out? What do you think?

from → 1
49 Comments leave one →
  1. rjlipton permalink*
    January 12, 2010 8:40 am

    Fixed a few typo’s.

    Reply
  2. Complexity Student permalink
    January 12, 2010 8:43 am

    Given your involvement with the subject, I feel you should give your students both a historic flavor of the subject which enables them to think like a theorist.

    Also, dwelling entirely on past might not be fruitful as you might miss out on the latest trends like the supreme robustness of PSPACE as enshrined in the FOCS 2009 paper which says that QIP = IP = PSPACE.

    These are two seemingly contradicting goals. I do not know how to do that. I hope you might.

    Reply
    • rjlipton permalink*
      January 12, 2010 8:47 am

      I plan to lecture on history and stories like I do here. I will cover some new material as time allows. But, I think they need to know the basics. In an algebra class we insist that you know what an ideal is and what a ring is and so on. I think the same is true here.

      But, thanks for taking the time to respond. I am trying something a bit new and your comment is just what I wanted. Thanks again.

      Reply
  3. Harrison permalink
    January 12, 2010 10:10 am

    I wonder whether the best way to teach the material is really to ask students to know X, Y, and Z proofs in detail. After all, optimally you want them to understand why a proof works, and how the method can be extended to prove other theorems and, best of all, what its limitations seem to be. I feel like it’s possible to understand the method of a proof without remembering the exact details, even for short combinatorial/complexity proofs. (For instance, the proof of Savitch’s theorem can be reasonably well-summed-up by the slogans “Introduce a new parameter” and “Divide and conquer.”) But for a basic graduate course, it probably doesn’t make too much difference.

    The combinatorialist in me is disappointed not to see Razborov-Rudich or the polynomial method in circuit complexity, but there seems to be not much emphasis on circuit complexity in general, so it’s at least understandable.

    Overall, it looks like a very good course, one that I wish I could have taken. One nitpick, though: I’d say “graph non-isomorphism,” since “non-graph isomorphism” sounds like you’re testing two things which aren’t graphs for isomorphism. Which I don’t think is even decidable, in general (for finitely presented groups, right? Although maybe that’s cheating.)

    Reply
  4. Jonathan Katz permalink
    January 12, 2010 10:20 am

    Structuring a course in this way is a great idea.

    I wonder, though, is your goal to teach the complexity theory that a general computer scientist should know, or the complexity theory that a theorist should know? A small number of the topics you list seem appropriate for the latter but not so critical for the former.

    Reply
  5. Jonathan Katz permalink
    January 12, 2010 10:22 am

    I’m also curious why you include space-bounded derandomization but not time-bounded derandomization (Nisan-Wigderson).

    Reply
    • rjlipton permalink*
      January 12, 2010 11:55 am

      I am working on the list. I like your suggested change. Also the target audience question is unclear.

      Reply
  6. Kurt permalink
    January 12, 2010 12:33 pm

    I hope that once you’ve taught the class, the lecture notes will be made available online, because it sounds like a great class!

    Reply
  7. luca permalink
    January 12, 2010 12:44 pm

    What is “Levin’s theorem”? It seems to be an underspecified description.

    Reply
  8. John Sidles permalink
    January 12, 2010 12:53 pm

    That syllabus at the end of the post is *great*! Gee, I wish that I knew everything on it … or at least could instantly look up the individual syllabus topics …

    So here is a suggestion that worked well for our seminar So you want to be a quantum systems engineer: without altering the syllabus at all, make every technical term a hyperlink to an appropriate section of an appropriate Wikipedia article.

    This IMHO would be a *great* (and well-posed) project for a team of students in your class … especially if they we instructed to (carefully and respectfully!) edit and/or write appropriate sections of Wikipedia.

    Reply
  9. Carl Lumma permalink
    January 12, 2010 2:03 pm

    I think it’s perfect, and I think you should write it, keeping the FAQ format, with each answer 3 paragraphs or less (not counting equations or images) + 2 or fewer “further reading” references.

    Reply
  10. Josh permalink
    January 12, 2010 3:37 pm

    I like the list! I would add a few related items (which maybe you had in mind to do anyways):

    1) Along with GNI in AM, the easy consequence that this means that if GI is NP-complete the PH collapses to the second level. This is “concrete” evidence that GI is not NP-complete (at least, according the conventional wisdom :)).

    2) Along with the nondeterministic time hierarchy: an oracle where NEXP is i.o.-contained in NP (or maybe that’s “contained in i.o.-NP”). This is a very easy oracle, and gives students a concrete example to think about when they wonder “is worst-case, almost-everywhere complexity really the right notion”?

    3) You might want to include RP and/or ZPP on the list of “known relationships between these classes”? Also, if NP is contained in BPP then NP=RP.

    4) I’m surprised not to see “linear programming is in P; integer programming is NP-complete” on the list of results whose statements should be known, at the very least.

    If the audience includes more budding complexity theorists, and you have time, you might also consider adding:

    5) Kolmogorov complexity and some of its relationships with complexity theory

    6) Bshouty et al.’s circuit-learning algorithm and some of its complexity-theoretic consequences. (An easy consequence that’s related to GNI in AM is Agrawal and Thierauf’s result that formula non-isomorphism is in AM^NP and hence cannot be \Sigma_2^p-complete unless PH collapses.)

    7) Some natural problems that are complete for levels of PH beyond the first, aside from just \Sigma_k SAT (there are a couple of papers by Schaefer and Umans on this).

    Reply
    • rjlipton permalink*
      January 13, 2010 4:55 pm

      Great ideas. I plan to refine the list this weekend. And will share will everyone. LP I think is in other places, but IP should be known to them.

      Reply
  11. proaonuiq permalink
    January 12, 2010 3:58 pm

    Definitions: NC hierarchy (which is not totaly captured by NL). In the multicore era, if BQP is, NC must be.

    Theorems: Ladner´s, Schaefer´s, Mahaney´s and Yin-ji Cai-Sivakumar.

    Conjectures: besides the incumbent, NC!=P. Isomorphism conjecture…or this is considered as history ?

    Reply
    • E.Hirsch permalink
      January 19, 2010 5:55 am

      – I would remove BQP from the list. I would not expect its definition will give any intuition to students, especially students who did not take quantum physics courses (is it a requirement?).
      + I would add NC along with examples.
      + I would add the (simple) connection between search and decision (or is it already here and I missed it?).
      + #12 (definitions) surely should have Bounded Halting in it (I feel it is implicitly there anyway).
      + I would add Valiant-Vazirani lemma (with proof).

      Reply
  12. Jeremy H permalink
    January 12, 2010 4:38 pm

    “But, more importantly, if they know this basic material they will know what complexity theory is all about. This is the main goal of the class.”

    One of the primary challenges I faced as an undergrad (and continue to face as a first-year grad student) is simply figuring out what subfields are out there. This class, even though technically “Intro to Complexity Theory” is most likely the de-facto “Intro to Theory”.

    I would love to see the course contain a survey of other branches of theory. A non-exhaustive list might include
    – Distributed Computing [FLP impossibility]
    – Crypto [Fully homomorphic encyrption, connection to BPP ?= P, …..]
    – Sublinear Algorithms [Approximate the minimum spanning tree in O(1) time]
    – Algorithmic Game Theory

    Such a survey seems far more useful than Fischer-Pippenger, although I’m not sure what else I would cut from your list to make room.

    Reply
  13. RodneyK permalink
    January 12, 2010 7:22 pm

    This looks like a very interesting course—are the lecture notes posted?

    Reply
    • rjlipton permalink*
      January 12, 2010 7:34 pm

      Not yet. Will try to.

      Reply
      • B. permalink
        January 13, 2010 9:56 am

        Why not post this lecture notes on your blog, as Terry Tao does via Luca Trevisan’s LaTeX2WP software? I find this a nice way to spread lecture notes to the community!

  14. npeqpcp permalink
    January 12, 2010 8:11 pm

    Should have Dinur’s np=pcp proof and Sudan’s list decoding.

    Reply
  15. Mihai permalink
    January 12, 2010 10:26 pm

    I would advocate for more nonuniform stuff. Communication complexity seems like something everybody should know. Branching program lower bounds should at least be mentioned.

    Reply
  16. Abhinav permalink
    January 13, 2010 12:11 am

    Professor,

    When you say “what the students should know”, do you mean “as a prerequisite” or “after they’ve had such a course”? I’m sorry, but I didn’t exactly understand.

    Reply
    • rjlipton permalink*
      January 13, 2010 7:57 am

      What they should know at the end of the course.

      Reply
  17. DS permalink
    January 13, 2010 12:13 am

    Even though it’s a bit of a detour into logic, Fagin’s theorem is just beautiful, tying computational complexity to expressibility (a la the equivalence between FSMs and Regular Languages, PDAs and CFLs).

    The relationship between parallel complexity, circuit depth, and how those classes interlace nicely with the space-bounded complexity classes (Nick’s and Steve’s).

    Another nice, rare, and definitive result to do is Fortnow’s (+ follow-ups), which shows, e.g., that SAT (and hence NP) is not in D-Time-Space [ n polylog(n), n^{0.99} ]. The result builds on Kannan’s, and the consequence for NP comes from Pippenger-Fischer.

    The complexity class TFNP (Megiddo–Papadimitriou), which shows that not everything fits nicely within the [DNA]TIME/[DNA]SPACE framework.

    How, of the four problems that highlighted the power of randomness ten years ago, two are not open any more! (I am, of course, referring to Primality in P, Undirected Connectivity in Logspace, with the open ones being Graph Non-Isomorphism in NP and Perfect Matchings in NC).

    Reply
  18. DTML permalink
    January 13, 2010 5:48 am

    I definitely suggest the beautiful Barrington’s theorem to be added into “Results That Are Important” or “Proofs That Are Important”.

    Reply
    • rjlipton permalink*
      January 13, 2010 1:37 pm

      Many good suggestions. I will work on adding etc and create a new list. Thanks.

      Reply
    • Jonathan Katz permalink
      January 13, 2010 9:54 pm

      While Barrington’s theorem is indeed beautiful, is it really something that a non-theorist should take away from their first (and probably only) course in complexity?

      Reply
      • lylebot permalink
        January 13, 2010 11:51 pm

        I learned Barrington’s theorem, and I’m not a theorist. Then again, I took the class from Barrington. 😉 But seriously, I’m glad I learned it.

      • DTML permalink
        January 14, 2010 5:34 am

        @ Jonathan Katz: I really like your complexity theory CMSC 652 course notes. One of the most lucid notes I could find on the web. I really appreciate your effort to simplify the proofs and your generosity to keep the notes available on the web!

  19. GASARCH permalink
    January 13, 2010 1:45 pm

    You say you will teach PCP which is great (I assume the statement and
    some of the proof ingredients but not the full proof.)

    You should also do the lower bounds on approx that come from PCP.

    bill gasarch

    Reply
  20. Kenneth W. Regan permalink
    January 13, 2010 10:32 pm

    Good suggestions enough to fill out two or three courses, methinks! In Buffalo we have a 5xx computability + complexity core-course that is required for all PhD students and an algorithms/theory core option for MS students. Half the term doesn’t leave time for everything in Dick’s syllabus, so we have two main 6xx complexity courses for algorithms/theory graduates. I’m teaching the one this term that emphasizes the classes below P. In tailoring the syllabus I’m facing choices of how to divide time between e.g. logic/descriptive complexity and communication complexity. Hence it is interesting for me to see comments like the positive voice for Fagin’s Theorem.

    Reply
  21. Marios Mavronicolas permalink
    January 14, 2010 1:47 am

    Well, the suggestions made so far are excellent and definitely
    add material for more than one course (and perhaps for more than two) …. If you still like to have more suggestions, here is
    another:

    Elaborate more on the TFNP class of Megiddo/Papadimitriou, and
    its basic properties. This being a semantic class, cover some
    of its subsclasses PLS and PPAD (and perhaps some variants of
    the latter) and demonstrate their corresponding complete
    problems (choosing the most elementary ones). If time permits,
    cover FIXP (and the Etessami-Yannakakis result that PPAD is a
    fragment of it).

    I see it is not yet customary to cover total function classes
    (such as TFNP, PLS, PPAD) in the basic complexity theory class.
    In my opinion, their importance is comparable to the more traditional
    ones that are either “more-to-the-inside” of NP (eg NC, NL etc) or
    “well-outside” (EXP, PH etc) of NP. They could be presented as
    the spectrum of (F)NP that is “opposite” to the (F)NP-complete problems: it contains (total search) problems that cannot be NP-hard (unless P=NP) …

    Reply
  22. Jörg permalink
    January 14, 2010 4:07 am

    Although I am not very experienced in complexity theory, I have got a small suggestion for you.
    What I think is missing is a short excursion into the domain of function problems. Or better yet, call them search problems!

    During the time of my undergraduate course I used to wonder why all the hard problems (like factorizing numbers) are cut down to decision problems. The inherent nature of such problems is to search for a solution (finding the prime factors), not do decide whether a solution exists.
    In my opinion, the missing link between theoretical analysis of computational problems (in the form of decision problems) and the (rather practical) analysis of algorithms is the description by complexity classes for search problems.

    What do you think?

    Reply
  23. David Wind permalink
    January 19, 2010 11:42 am

    Which book – if any – do you plan to use for this course? More generally, what are the good introductionary books on complexity theory out there?

    Reply
    • rjlipton permalink*
      January 19, 2010 5:58 pm

      The new book by Arora and Barak.

      Reply
  24. Venkatesh G permalink
    January 29, 2010 10:21 am

    where can i get the access to lectures of this course ? is it available in your blog?

    Reply
  25. Jeffrey Shallit permalink
    April 1, 2010 10:26 am

    There is some biographical information about Cobham and a picture here.

    Reply
  26. Steven Twentyman permalink
    June 30, 2010 5:52 pm

    Hello.

    What if, in a general theory of everything kind of way, some singular human conscious had used simple Yes(I should feel guilty) or No(I do not feel guilty) answers to answer every moral question that he could remember that had ever occurred in his life. In this way he could have become completely pure. He would have truly asked himself all the questions that could be asked of him. He would have emotionally evolved back to when he was a child.

    What if he then assigned an ‘It doesn’t matter as life is only made to make mistakes’ label on every decision that he had analysed.

    This would not make him God or the devil, but just very still and very exhausted. Anybody can do this but just for the purpose of this experiment lets say I have done this. Which I have.

    There are no fears in me and if I died today I could deal with that because who can know me better than myself? Neither God or the Devil. I am consciously judging myself on ‘their’ level.

    To make this work, despite my many faults, take ME as the ONLY universal constant. In this sense I have killed God and the Devil external to myself.The only place that they could exist is if I chose to believe they are internal.

    This is obviously more a matter for a shrink more than a mathematician, but that would only be the case depending on what you believed the base operating system of the universe to be. Math / Physics / morals or some other concept.

    As long I agreed to do NOTHING, to never move or think a thought, humanity would have something to peg all understanding on. Each person could send a moral choice and I would simply send back only one philosophy. ‘ LIFE IS ONLY FOR MAKING MISTAKES’.

    People, for the purpose of this experiment could disbelief their belief system knowing they could go back to it at any time. It would give them an opportunity to unburden themselves to someone pure. A new Pandora’s box. Once everyone had finished I would simply format my drive and always leave adequate space for each individual to send any more thoughts that they thought were impure. People would then eventually end up with clear minds and have to be judged only on their physical efforts. Either good or bad. It would get rid of a lot of maybes which would speed lives along..

    If we then assume that there are a finite(or at some point in the future, given a lot of hard work, there will be a finite amount) amount of topics that can be conceived of then we can realise that there will come to a time when we, as a people, will NOT have to work again.

    Once we reach that point we will only have the option of doing the things we love or doing the things we hate as society will be completely catered for in every possible scenario. People will find their true path in life which will make them infinitely more happy, forever.

    In this system there is no point in accounting for time in any context.

    If we consider this to be The Grand Unified Theory then we can set the parameters as we please.

    This will be our common goals for humanity. As before everyone would have their say. This could be a computer database that was completely updated in any given moment when a unique individual thought of a new idea / direction that may or may not have been thought before.

    All that would be required is that every person on the planet have a mobile phone or access to the web and a self organising weighting algorithm biased on an initial set of parameters that someone has set to push the operation in a random direction.

    As I’m speaking first I say we concentrate on GRAINE.

    Genetics – Robotics – Artificial Intelligence – Nanotechnology and Zero Point Energy.

    I have chosen these as I think the subjects will cross breed information(word of mouth first) at the present day optimum rate to get us to our finishing point, complete and finished mastery of all possible information.

    Surely mastery of information in this way will lead us to the bottom of a fractal??? What if one end of the universes fractal was me??? What could we start to build with that concept???

    As parameters, we can assume that we live only in 3 dimensions. We can place this box around The Milky Way galaxy as this gives us plenty of scope for all kinds of discoveries.

    In this new system we can make time obsolete as it only making us contemplate our things that cannot be solved because up to now, no one has been willing to stand around for long enough. It has been holding us back.

    All watches should be banned so that we find a natural rhythm with each other, those in our immediate area and then further afield.

    An old clock watch in this system is should only be used when you think of an event that you need to go to. It is a compass, a modern day direction of thought.

    A digital clock can be adapted to let you know where you are in relation to this new milky way boxed system.(x,y,z).

    With these two types of clocks used in combination we can safely start taking small steps around the box by using the digital to see exactly where you are and then using the old watch to direct you as your thoughts come to you.

    We can even build as many assign atomic clocks as are needed to individually track stars. Each and every star in the Milky Way galaxy.

    I supposed a good idea would be to assume that I was inside the centre of the super-massive black hole at the centre of the galaxy. That would stop us from being so Earth centric.

    We could even go as far as to say that we are each an individual star and that we project all our energies onto the super-massive black hole at the centre of the galaxy.

    You can assume that I have stabilized the black hole into a non rotating perfect cube. 6 outputs /f aces in which we all see ‘the universe and earth, friends’ etc. This acts like a block hole mirror finish. Once you look it is very hard to look away from.

    The 6 face cube should make the maths easier to run as you could construct the inner of the black hole with solid beams of condensed light(1 unit long) arranged into right angled triangles with set squares in for strength.

    Some people would naturally say that if the universe is essentially unknowable as the more things we ‘discover’ the more things there are to combine with and therefore talk about. This is extremely fractal in both directions. There can be no true answers because there is no grounding point. Nothing for the people who are interested, to start building there own personal concepts, theories and designs on.

    Is it possible that with just one man becoming conscious of a highly improbable possibility that all of universes fractals might collapse into one wave function that would answer all of humanities questions in a day? Could this be possible?

    Answers to why we are here? What the point of life really is et al?

    Is it possible that the insignificant possibility could become an escalating one that would at some point reach 100%???

    Could it be at that point that the math would figure itself out so naturally that we would barely need to think about it. We would instantly understand Quantum theory and all.

    Can anybody run the numbers on that probability?

    Reply
  27. snappywan permalink
    July 26, 2010 7:34 am

    Would you ever consider teaching an online course at universityofreddit.com?

    Reply
  28. yoinkflotsam permalink
    July 27, 2010 5:48 pm

    I encourage your efforts. Please continue teaching us all.

    Reply
  29. John permalink
    April 3, 2016 12:48 pm

    There is a picrure of Cobham on https://en.wikipedia.org/wiki/Alan_Cobham

    Reply
  30. steve uurtamo permalink
    September 2, 2019 9:51 am

    Getting through AM in the first semester, along with some of the circuit results, Toda’s theorem, etc. is pretty quickly-paced. How did it work out?

    Reply
  31. Rao permalink
    September 17, 2019 12:55 am

    “The picture is of Jack, not Alan: there seems to be no picture available of Cobham.”

    Cobham’s picture is available on this blog page (this posting was three months later than your blog entry):

    http://recursed.blogspot.com/2010/04/alan-cobham.html

    Reply

Trackbacks

  1. Knowing .NET » Blog Archive » Complexity Theory is … Complex
  2. Tweets that mention A Course on Complexity Theory « Gödel’s Lost Letter and P=NP -- Topsy.com
  3. uberVU - social comments
  4. The complexity class « Qleafriver's Blog
  5. The complexity class « Qleafriver's Blog
  6. joy of code 2014, imitation game with Turing, more diverse zeitgeist | Turing Machine

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading