A Little Bit Of (Computability) Theory

When most people think of Computer Science, the first thing that pops into their head is an image of some greasy kid in a black t-shirt and sandals tippity-tappity typing away. While programming is a fundamental tool in the computer scientist’s kit, it’s no more the core of Computer Science than glassware is the core of Chemistry. In truth, the fundamental quality of all rigorous sciences, from the abstract (Mathematics) to the “hard” (Physics, Chemistry) to the “fuzzy” (looking at you, Psychology!) is that they all postulate fundamental truths about their area of study.
In Computer Science, these fundamental truths are based on assertions about the ability of a computational system to be able to solve problems. There are some problems which are inherently unsolvable by computational systems, either due to physical limitations (memory, processing speed, etc) or theoretical boundaries. For example, let’s take three problems which we might want to give our computer to solve:

  1. We’d like to know how much time a ball dropped from rest takes to fall 3 meters on Earth.
  2. We’d like to know what the shortest path between the 100 largest cities in Germany is that passes through each city exactly once and begins and ends in the same city.
  3. We’d like to know, once we have written a program, whether or not it will run for a finite period of time or enter into an infinite loop.

These three problems illustrate three very different classes of computability. The first is in the class commonly referred to as P: Deterministic Polynomial Time problems. These problems execute in an amount of time which has an upper bound given by some polynomial in the number of inputs. In simple terms, this means that the amount of computation required to solve a problem doesn’t grow too quickly for more inputs. These include constant time problems, which can be solved in the same amount of time for any number of inputs (think “find the nth number in an array”); logarithmic time problems (Quicksort); and polynomial time problems (Bubble Sort). This is generally the category we want to be in.

Our first problem is in P because it can be solved in a constant number of steps. Unfortunately, our second problem is significantly more complex: it actually is bounded in its execution time by a function of the form O(CN!) where C is a constant and N is the number of cities. We can solve this problem, but it will take an extremely long time for even moderately sized inputs. For example, the problem as we stated above would take as many as 9 x 10^157 steps to solve for the unique ideal solution. This class of problems is called NP, for Nondeterministic Polynomial Time. These problems are extraordinarily difficult, and for larger input lengths are effectively impossible to solve in a reasonable amount of time. NP is commonly considered a superset of P, meaning that every problem contained in P is also contained in NP, although this is as of yet unproven. In fact, one of the major outstanding problems in Computer Science is to prove this conclusively one way or the other. The problems in NP are important but difficult to compute; if one could find polynomial time algorithms for them it would be a huge advance in our computational abilities!

Finally, the last example demonstrates one of the fundamental weaknesses of current computers: this problem is not solvable for all possible inputs. It joins a class of problems which, despite our best efforts and algorithms, are fundamentally impossible to compute answers for (say, counting the number of atoms in the universe). While our techniques are powerful, there are inherent limits on what we can do with computers, and Computational Complexity Theory aims to find out what they are.

Advertisements

A Short Tutorial on Eclipse/EGit/GitHub

I wrote this to help out some of my collaborators on our AI project for class, but I figure it might help some other people get started using version control.

Step 1: Get Eclipse

If you don’t want to work in Eclipse, that’s fine; you can access the source files directly without it. You will, however, need to look up how to generate SSH keys for your platform and how to set up Git on your own. GitHub has a nice tutorial after you sign up; so skip to step 2 and then take it from there.

If you do want to work with Eclipse, download the latest version here: http://www.eclipse.org/downloads/ and get the Eclipse IDE for Java Developers. Once you have it downloaded, extract it to someplace you will want to keep it, and double click on the eclipse icon to start it. We need to install the EGit plugin to use Git from Eclipse, so go to the “Help” menu item and click on “Eclipse Marketplace”. Search for EGit, and install it (it should be the only item that comes up). Restart Eclipse when it prompts you to.

Eclipse is a powerful development environment because it’s open source and has a ton of plugins for development; but that also makes it slow sometimes. Let’s make it go a little quicker. Go to the “Window” menu and click on “Preferences”. In the window that opens up, expand the “General” item, and go to “Startup and Shutdown”. This will show all the plugins that get started with Eclipse. Unselect all of them and click Apply”.

Ok, now that we’re in our settings panel, go to “Network Connections” and expand it. It’s under “General”. Click on “SSH2”, and move to the key management tab. IF YOU ALREADY HAVE A PUBLIC/PRIVATE SSH KEY GENERATED, SKIP THIS STEP. IT WILL OVERWRITE ANY EXISTING KEYS, AND YOU WILL NOT BE ABLE TO USE THEM ANYMORE. Otherwise, click on “Generate RSA Key…” It will create a public/private key for you; copy the public key from the text area and hold onto it. Don’t do anything more with Eclipse at this point; we need to set up our GitHub account before we go further.

Side Note:
If you already have a public/private key pair, you can open up the public key file (should be in /home/yourusername/.ssh/id_rsa.pub on Linux) and copy it for the next step.

Step 2: Getting Your Account Set Up

Ok, first things first: We need to set up a GitHub account. To do this, go to the main page at http://www.github.com and click on “Plans, Pricing and Signup” in the middle of the page. (It’s big and blue.) At the top of the next page, it has a free hosting plan above all the paid ones; click on “Create a free account”. Type in your username, email, and password (Generally, using your real name is a help in these kinds of things, since employers/future project leaders/current collaborators can tell who you are and what you’ve worked on) and click “Create an account”.

Cool! So we have an account. Next thing to do is set up our SSH key. Go to “Account Settings” at the top of the page click on it. On the left sidebar is an option “SSH Public Keys”, click on that. We’ll want to set up another key, so click on “Add another public key”. Give it a descriptive name in case you need to modify it, and paste the public key from Step 1 into the big box. Save the key, and you’re done! If you haven’t saved your key in Eclipse, go back and do that now. Click “Save Private Key”, and put it into the default folder. If you want to put a passphrase on it, I encourage you to do so; if your private key gets stolen the thief has your identity and access to any server that uses that key.

Source at GitHub

Hey all,

I know it’s been a while since I’ve written anything, but today I’ve got something good for you. I’ve started some projects which I feel comfortable sharing with the world, and I’m doing just that. I’ve created repositories for two new projects, one a physics library for Java, and the other the class projects I’m doing for this block’s course CP365: Artificial Intelligence. I’ve already used it to store the source for today’s project (a swarm of boids showing emergent behavior), and I’ll continue to upload source to it as I work on more assignments. If you’re interested, you can check out the source here:

Physics

Artificial Intelligence

-Nick

[EDIT]

I’ve also put the code for my rendering project up: https://github.com/nickpascucci/Render