CACL: Computability and automatic complexity lab

Team members

  • Bjørn Kjos-Hanssen (Professor)
  • David Webb (Ph.D. student) computability theory
  • Samuel Birns (Ph.D. student)
  • Taqui Raza (M.A. student) web semantics

Recent members

  1. Achilles Beros, Temporary Assistant Professor, 2015-2018 in progress
  2. Mushfeq Khan, Temporary Assistant Professor, 2014-2018 in progress
  3. Kaui Yogi, M.A. 2018 in progress
  4. Lei Liu, M.A. 2017
  5. Paul Kim Long V. Nguyen, Ph.D. 2014
  6. Malihe Alikhani, M.A. 2014
  7. Jason Rute, Junior Researcher, 2013
  8. Kayleigh Hyde, M.A. 2013
  9. Cameron Freer, Junior Researcher, 2010-2011
  10. Quinn Culver, M.A. 2010
  11. Katie Brodhead, Temporary Assistant Professor, 2008-2009

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.