Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Do Wikis Work?

Expand Messages
  • Lance
    John Stockton put a wiki version of the Complexity Zoo on the Quantum physics Qwiki . For those not up on the nomenclature, a wiki is a specially designed web
    Message 1 of 1 , Sep 8, 2005
    • 0 Attachment
      John Stockton put a wiki version of the Complexity Zoo on the Quantum physics Qwiki. For those not up on the nomenclature, a wiki is a specially designed web page that anyone can change usually with mechanisms for tracking and undoing those changes if necessary. Ideally a wiki will allow the zoo to remain up-to-date without continual intervention from Scott. But will it work?

      The Wikipedia has a number of entries for various complexity classes. I generally find them for the most part accurate but not complete. Take for example the NL entry which doesn't note that NL is closed under complement but instead has the misleading result that RL=NL (where one allows the randomized machine to have infinite computation paths). Sure I could fix the entry in wikipedia but there are at least two problems:

      • There aren't enough people in the field who have the time and patience to go through all the entries and update them.
      • I firmly believe RL should be what Wikipedia calls RLP. But what right do I have to impose my naming conventions on the whole wikipedia universe.

      Sanjeev Arora and Boaz Barak set up Theory Matters as one big wiki. Boaz once said the following in a weblog comment.

      Don't give "theorymatters.org" as an example to a place that ignores area X. It's a Wiki - if you don't add the material yourself no one will do it for you.
      But people are reluctant, for whatever the reason, to edit the wiki. Outside of the "Survey Collection" you can nearly count the number of contributors to the wiki on one hand.

      In short wikis, like anything else on the web, can be a good source of information but are often incomplete sometimes in important ways. Just because anyone can edit a wiki doesn't mean that they do.

      --
      Posted by Lance to Computational Complexity at 9/08/2005 05:44:00 PM

    Your message has been successfully submitted and would be delivered to recipients shortly.