Computer Science Blows My Mind

posted by Craig Gidney on May 2, 2013

Computer science is an interesting discipline. Often, I find myself inadequately trying to communicate why I find it so fascinating. I think I get the closest when describing computer science things that ‘blow my mind’.

This post is… basically just a list of computer science things I think are cool.

Physical

I remember a time when I was very confused about how computers worked. I knew I could type in a program, and the computer would run it, but how that happened was a big mystery. I could write a program to interpret programs, but… how do I run the interpreter? It can’t be interpreters all the way down!

When I learned how to make an adder out of logic gates, and realized I could pull the same sort of trick all the way up… I imagine that’s how Archimedes felt as he ran through the streets naked after realizing he could measure volume via water displacement.

It sounds a bit silly to say it, but did you know computers run on physics?! Amazing!

Coloring Complexity

Suppose you’re given a map. Your job is to determine if, with a particular number of colors, you can color in all the areas without giving any bordering areas the same color. You don’t have to actually provide such a coloring, just determine if there is one.

How difficult do you think it is to solve this problem? It actually depends on the number of colors.

With 0 or 1 colors, the problem is trivial. Only graphs without nodes are 0-colorable, and only graphs without edges are 1-colorable.

With 2 colors, the problem is easy. You can solve it in linear time. As soon as you pick the color of one area, you’re forced to a single possibility for adjacent areas. Just keep filling in areas as you’re forced to, until you either finish or find a contradiction.

With 3 colors, the problem is very hard. In fact it’s NP-Complete, meaning an algorithm that solves any instance in polynomial time could be repurposed to say… be the first to find inputs that collide when hashed with SHA-1.

With 4 colors, the difficulty changes again. Complicated details aside, you can use the following algorithm to solve the problem:

bool IsFourColorable(PlanarGraph g) {
    return true;
}

Needless to say, planar 4-colorability is a bit easier than planar 3-colorability.

Over-constrained problems are easy, but so are under-constrained problems. Changing tiny details of problems can massively change how easy they are to solve.

Proofs without Proofs

Suppose you meet an alien with access to absurd amounts of computational power. The alien is cooperative, but you’re not sure if it’s trustworthy. Can the alien help you solve hard computational problems, even though you don’t trust it and it can probably track everything you do? Can Arthur extract useful work out of a tricky Merlin?

Welcome to the wonderful world of interactive proofs.

Want to convince me that you have solved a problem or know some information (e.g. a password), without giving me the solution or the information? You can do it with an interactive zero knowledge proof. For example, most cryptographic voting systems involve voting machines zero-knowledge-proving that they are functioning correctly at every step.

Want to search throughall the different possibilities that could be reached in exponential time, to see if one meets a criteria? All you need is two isolated provers instead of one. No, seriously, MIP (problems solvable in polynomial time with multiple unbounded interactive provers) is equivalent to NEXPTIME (problems that can be solved in exponential time, with access to a ‘branch both ways’ instruction). This is not quite as practical as zero knowledge proofs, but NEXPTIME is so gigantic that I don’t care.

In computer science, the idea of a mathematical proof is one special case amongst many strategies to convince verifiers that something is true.

Secure Multiparty Computation

A common intuition in real time strategy games is that map hacks are unavoidable. The game needs to know where enemy units are in order to determine if they can be seen, and a map hack is just a matter of displaying instead of hiding the information… right? Wrong.

Secure multiparty computation (SMPC) allows mutually distrusting computers to interact in a way that simulates a trusted server. In the case of an RTS game, the simulated server would compute the answers to questions like “What units can see each other?” and then tell the players what they can see. This can be done without any of the players’ computers learning where hidden enemy units are.

Unfortunately, SMPC is quite expensive and requires back-and-forth interaction. It’s not practical to run it over hundreds of unit positions a hundred times a second. It’s more applicable to turn based games like civilizations or poker than to real time strategy games.

Still, the fact that having a real trusted third parties is unnecessary (it’s more like… an optimization) is very cool.

Halt

You’ve probably head of the halting problem. Basically, it’s a more concrete version of Gödel’s incompleteness theorem: instead of proving xor disproving every statement, you want to find a program that determines if given programs halt.

It is the case that no program solves the halting problem. This is quite possibly the most actively counter-intuitive thing I know.

For example, you can write a (partial) halting solver that works by enumerating all mathematical proofs until a proof that the program in question halts is found or a proof that the program in question doesn’t halt is found. The only way such a solver can fail is if there are “unfathomable” programs that run forever, with no possible proof even in principle that they run forever. (Alternatively: you used an inconsistent proof system.)

Unfathomable programs exist.

The idea of unfathomable programs breaks my brain. Again and again, I end up with the same confused questions: if there’s no proof the machine doesn’t halt, in what sense does the fact that it doesn’t halt even exist? How does it make any sense to require an infinitely large proof about any aspect of a machine with a finite-sized specification?

Even worse, unfathomable programs are impossible to find. Confirming you had a no-proof-but-runs-forever program would involve proving it ran forever and then proving you didn’t just prove that last thing.

Basically, the halting problem can be used to produce the feeling of confusion-about-reality-itself on demand. It’s just that mind blowing to me.

Summary

Computer science interesting. Craig like.

Discuss on Reddit

  • Mark

    If someone claimed to have a black box that solved the Halting Problem, is there an interactive proof they could offer to convince someone of that?

    • CraigGidney

      I don’t see any way to do it. We could test the box against programs with known halting/not-halting, we could test if the box solves NP-Complete problems reduced to halting queries, and we could do some measure of testing by just running programs for a really long time and comparing… but none of those allow us to become arbitrarily certain that the box works in the cases that we can’t figure out ourselves.


Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Archive