There is an algorithm that can, at least in theory, and in likelihood, at most in theory, solve any problem, calculate the meaning of life, or simulate the universe even …

## Articles in the Computer Science category

## Hamiltonian Cycle hardness and gadgets

One of my preferred types of NP hardness proofs involves gadgets. Some publications prefer the more general terminology *components*, but I’ll use the former. Gadget-based proofs, with the proper …

## Pseudo-polynomial computational complexity

Exploring the definition and implications of pseudo-polynomial asymptotic time complexity.

## The ever common Knapsack problem

We encounter the Knapsack problem all the time. Given a set of items, each of a specific size and value, is it possible to fill a limited size knapsack with …

## Fun with self-referential paradoxes and the halting problem

I want to explore a set of paradoxes that arise from self-referential problem formulations. I will then proceed to present the paradox in a more formal setting of computability theory …

## About Lisp and programming languages

How Lisp re-sparked academic excitement in a programming language.

## Kultur und Informatik 2018

I attended the 16th annual Culture and Computer Science conference in Berlin, organized in Schloss Köpenick, a beautiful art museum setting along a river. The smaller conference focuses on the …

## Space vs Time

On space complexity with respect to time, and their trade-offs.

## Subset Sum problem NP-hardness proof

I never expected to dedicate a casual blog entry to a hardness proof, especially one fairly academic as this. However, the nature of it evokes certain elegance beyond what I …

## On Computational Complexity

I want to highlight the branch of Theoretical Computer Science concerned with classifying algorithmic complexity. Similar to the previous post on computability, this serves as a more philosophical complement to …

## About Computability and Turing Machines

On the beauty, simplicity and utility of a Turing Machine.