> Most people can understand what an algorithm is, some basic problems like sorting a list or TSP.
Not sure I agree with this. Maybe most people have a vague idea of an algorithm as "something a computer does". Most people I don't think would grasp that you can have fundamentally different algorithms to solve the same problem.
> Most people I don't think would grasp that you can have fundamentally different algorithms to solve the same problem.
Most people do grasp arithmetic though, and I think you could easily describe a parallel in math to explain how there are different ways to get the same result
10+5=15
20-5=15 as well but subtraction takes longer for the computer to calculate
1+4+7+3=15 too with only addition but it has multiple steps so it takes longer for the computer to calculate
I think most people could draw a very rudimentary understanding of how algorithms take different amounts of time from that explanation
I think you could explain it as the fastest possible computer program for doing the task. Not the fastest made, but the fastest that ever could be made.
Then you can talk about how this optimal program behaves. If you double the size of the input (people can understand this in terms of file size), does the time double, or quadruple, or...? I wouldn't mind trying to explain NP to a lay audience. I think you could get it across pretty well.
You can probably do Monty Hall by enumerating all of the possibilities. There are only nine possible combinations of where the car is and which door you choose. The difficulty, I think, comes from overanalyzing the problem, and a simpler explanation actually makes the job easier.
Relativity is a goo example though. I don't understand relativity beyond the most superficial level. As far as I can tell, the teenager-level explanations of relativity are not right. They convey some aspects of relativity on a conceptual level, and even some basic things on a mathematical level, but they're omitting important aspects of it. You might read A Brief History of Time (or whatever your favorite explainer is) and come away with an understanding of relativity, but your understanding will be some combination of wrong and extremely incomplete.
I'm not sure most people have any comprehension about how computers (as in the devices they use) work - but they definitely understand the concept of a list of steps being followed to carry out a procedure (just not necessarily the part where that's what computers do).
Phrase a search algorithm as finding out if a card exists in a deck of cards with the rule that you want to look at as few cards as possible is more likely to be useful than saying you have an array of data on a computer. (To be able to do this faster than "look at them all" you should probably also say the deck is sorted)