P v NP: A Modern Mystery

Marco Tamma on Flickr

Can we measure the time and steps required for things to happen?

Programming may seem magical, but at some point almost every programmer is going to hit against one big limitation: time. You can “solve” any problem in the world, but if your code takes years to finish it’s not really a solution anyone can use.

Programmers and computer scientists like to talk about the complexity of programs, both space and time complexity. Space complexity is about how much memory the program uses or, in other words, how much data it needs. We’re not going to talk about this much, instead focusing on time complexity.

We don’t tend to measure time complexity in terms of time but rather in terms of how many steps something takes. Steps are a better measurement since the number of steps-per-second processors can calculate goes up every year, but the steps don’t change over time. Further, we don’t even need to be particularly exact in measuring how many steps the program takes. We just need a rough measurement in terms of the “size” of the problem we’re working on.

For example:

  • the length of the list we’re sorting
  • the number of accounts in the database we’re searching
  • the number of computers in the network when we plan how to efficiently send data over the internet
  • the number of variables in the system of equations we’re solving

To be specific, let’s consider a list of length n that we need to sort.

If we’re trying to figure out whether or not the sorting algorithm we want to use is feasible, or in other words it can finish in a reasonable time, we don’t actually care whether the number of steps an algorithm takes is 3*n or n + 100 or 20*n. What we care about is how fast the number of steps grows: whether it grows by 3*n or 20*n making the list ten times larger only makes the number of steps grow by a factor of ten. On the other hand, if your algorithm grows like 3*n^2 or 2*n^2 and you make the list ten times longer, it will take one hundred times longer to finish.

 

Become a subscriber and get access to the rest of this article. Plus all our magazine articles.

Stories also include numerous links to help parents, kids, and teachers learn more. Get access today at just $15 per year!

Subscribe Today!

Also In The June 2017 Issue

Building and creating your tools with the Minecraft toolbox helps you survive the game.

Sensors give robots the senses humans have.

30+ ideas for all age holiday gifts, from books to apps to board games to VR and more.

There might be a reason that too-real robot and video game character creeps you out.

This programming language uses colors instead of text and punctuation to add and perform other tasks.

Knowing how passwords are cracked can help you create better passwords.

There are a number of strategies teachers (plus parents and students) can take to learn programming.

This project uses conductive thread to create a glove to activates your phone.

Software programming does neat things with language, in this case, mixing capital letters.

This Scratch game has lots of ways you can customize the game play. No cats were harmed in the making of this article either.

Links from the bottom of all the October 2017 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for October 2017.