Computer Science - What's that?

I'm going to try to stick to posting every Wednesday. This post needs a lot more work, but my main goal is just to get a regular schedule going.

A lot of writing has been devoted to just explaining what computer science is or isn't. Some people even want to get rid of the term as a whole.

Here's my view on what computer science is, for a regular person who is curious. Computer science is a really broad field these days, but to really understand the core, it's good to start at complexity theory. It's not the most accurate use of the term, but I am talking about an area that deals specifically with problems and how they are solved by computers.

Why is this fun? I think that question isn't asked enough. Usually because serious science and fun aren't commonly associated. Puzzle solving is fun, and puzzle solving with computers is a new puzzle. Solving crosswords, jigsaw puzzles, and sudoku puzzles are pretty fun. After you start getting good, you develop a few rules that help you solve the puzzles faster.

Now, try to think of how you would get a computer to solve these puzzles for you. It spoils the fun of the original puzzle, but now you have a whole new set of tools to work with. Just like a sudoku puzzle, once you get good at solving it, you want to solve it faster. With a computer program, you have to count how many operations it is doing and try to squeeze that down. Even trying to count the operations is a puzzle in itself.

Consider this puzzle, you have a box with a row of switches, and a lightbulb. The game is to flip the switches to that the lightbulb turns on. Every time you add a switch, the number of combinations to try doubles. The boring way to play the game is to try all the combinations one at a time.

To make it more interesting, we can now see inside the box. The inside of the box is made up of the three basic pieces: AND, OR, and NOT. It's easier to describe these than a sudoku puzzle! Now that we can see that the box is made up of, is there a way to use that information to turn the lightbulb on in a way that is significantly faster than trying all the combinations? This puzzle is part of a whole class of puzzles that are called NP-complete, which most researchers suspect have no efficient solution, but have no way to show it.