CACL: Computability and automatic complexity lab


Team members

  • Bjørn Kjos-Hanssen (Professor)
  • Achilles Beros (Temporary Assistant Professor, 2015-2018) computability theory
  • Mushfeq Khan (Temporary Assistant Professor, 2014-2018) computability theory
  • David Webb (Ph.D. student) computability theory
  • Samuel Birns (Ph.D. student)
  • Lei Liu (M.A. student) automata and finance
  • Kaui Yogi (M.A. student) automata and finance
  • Taqui Raza (M.A. student)

Alumni et alumnae

This site

In the menu above, press "Complexities" for an autocomplete-based JavaScript app. Press "Witnesses" for a screensaver.

Complexity lookup over HTTP

Other sites

Bjørn Kjos-Hanssen (WordPress)

Automatic complexity in the cloud


  • Fixed minor bug in the screensaver.
  • Complexity witnesses by HTTP now included up to length 23. Check out for example
  • New version (Javascript) goes up to length 19. All info up to that length is in memory at the same time so it is a bit slow.
  • The web app works great in Opera! Not as well in Chrome, and not at all in Firefox.
  • The autocomplete works in the Chrome browser, but not in a good way: to see the complexity of the string 0 you first have to type 000000000 then delete several 0s. The Android app is better!
  • Because I uploaded data to Google's database via HTTP, only up to length 8 was possible, so that is the current length being used.
  • Using JavaScript (JQuery) to get the data from the Google App Engine database asynchronously, thus no info available in View Source.
011000111100000110       9
means that the string 011000111100000110 has complexity 9. An Android version for 0.99 USD is available in the Google Play Store.