Theory

Contains random thoughts on Theoretical Computer Science and Complexity Theory.

  • P vs NP in Images

    By Bobby on 2009-01-05 02:56:25.632111
    A while back i wrote some code for enumerating subsets and permutations of a given set. I was able to apply this to draw some images pertaining to the the question of P vs NP.

  • Low Bandwidth Networking

    By Bobby on 2009-01-04 18:55:49.836605
    I thought about this impractical yet interesting take on data transfer.

  • An NP-Complete Puzzle Game

    By Bobby on 2009-01-04 18:32:35.114278
    NP-Complete problems are some of the most difficult problems to solve in Computer Science that do come up quite often. Many popular games are known to be NP-Complete (such as variable sized Sudoku). Here i describe another NP-Complete puzzle game and a simple proof by reduction from the Clique problem.

  • Obtaining Subsets & Permutations

    By Bobby on 2009-01-04 08:34:13.028926
    It has happened in the past that i needed to either obtain all subsets or all permutations of a given set. Recently i took the time to implement a couple of algorithms in Java that do this.
    They are both recursive algorithms, an iterative approach would not be easy to implement in both cases.