Does Programming Help You Understand Complexity?

I got the following question in an email.

My nephew is currently in high school in China and has developed a strong interest in computer science and mathematics. Recently, we've been talking about how computers can solve incredibly complex problems, yet there are still some problems that even the most powerful computers struggle to handle efficiently. I work in backend data maintenance myself, so I often think about how much a system's performance depends on the way a problem is approached, rather than simply how powerful the technology is.

From your experience, what do you think is the most important thing a young student should understand about the limits of what computers can do? Would you encourage someone like my nephew to begin exploring these questions through mathematics and logical reasoning, or to start by writing programs and discovering the challenges through practice?

A great question with no perfect answer. For me, I did considerable programming in high school and college in the early days of personal computers. Computers were slow so you really had to optimize. I learned new algorithmic techniques mostly from talking to other programmers and there were some problems that the computers just didn't have enough time to solve. Those experiences definitely helped me have a good understanding of the power of good algorithms and the limitations of computing when I later went into theoretical computer science.

But many of my colleagues successfully went into the field from the mathematical side without much programming experience and did fine. 

My experience comes from a different time. Now computers are much faster and AI can just give you the best known algorithms. We have much better algorithms for NP-complete problems like Satisfiability. Unless you go looking for hard problems, you'll rarely hit one you can't solve.

Reminds me of when I took my daughter driving during a snow storm to teach her how to handle a skid. In an empty parking lot I told her to move fast and hit hard on the brakes. The car just stopped. She failed to learn because of anti-lock brakes.

Ultimately, to learn why some problems are hard, you need to understand some theoretical computer science, particularly why the halting problem is impossible to solve and why NP-complete problems are likely hard. How you get there depends on the person.

If your nephew likes to program, you can give him the challenge of trying to solve some SAT competition problems or solving some of the hard LeetCode problems. If he is more into mathematics, ask him to try to come up with a SAT algorithm mathematically so he understands how hard the problem is. The difference today is that you have to search out hard problems as it's just less likely to run into them naturally.