When that day comes, when people try to handle problems that cannot be solved by throwing hardware at them, algorithms will be only relevant factor. As more and more jobs become automated, but NP-complete tasks like Theorem Proving remain intractable for computers, the discovery of new algorithms will be a central task for human beings.
I think NP-complete problems are really interesting, because by definition they are all reducible to the same problem. (Formal definition here.) So, if a polynomial time algorithm is found for any NP-complete problem, then in theory an algorithm has been found for all the others.
However, a lot of NP-complete problems are not so hard for humans to figure out in specific cases. Sudoku puzzles are a good example of this—it's pretty easy to solve a Sudoku puzzle, but so far it has been impossible to find an algorithm for solving Sudoku problems in general in polynomial time. The reason for this is that we humans use a sort heuristic-based reasoning where we use some broadly applicable (but not universally applicable) "rules of thumb" to attack these problems in a sort of non-algorithmic way. This approach involves leaving out a lot of irrelevant information and getting straight to the crux of the problem at hand—something that can only be done in specific cases and not in general to NP-hard problems.
So, our best hope, in my opinion, for solving NP-hard problems is to take a more cognitive approach. That is, I think that we should model our algorithms for certain tasks that are well-suited to human brains after the strategies we use to solve them ourselves.
I haven't read Eric Baum's book which you mentioned, but I think that one of his claims is that humans are so successful at thinking because they leave out all the irrelevant possibilities just by the nature of how they evolved—they evolved in such a way that only the important possibilities are addressed in cognitive functioning.
Thus, I think that the algorithm design of the future should take into account traditionally "non-algorithmic" problem-solving strategies like the sort of probabilistic ones humans use in order to perform more efficiently. However, these new "algorithms" will not necessarily be provable to solve a problem, even if they can solve a certain class of problems most of the time. Hence, the way of gaining efficiency in this way will be sacrificing universal applicability in order to simplify the problem.
I think NP-complete problems are really interesting, because by definition they are all reducible to the same problem. (Formal definition here.) So, if a polynomial time algorithm is found for any NP-complete problem, then in theory an algorithm has been found for all the others.
However, a lot of NP-complete problems are not so hard for humans to figure out in specific cases. Sudoku puzzles are a good example of this—it's pretty easy to solve a Sudoku puzzle, but so far it has been impossible to find an algorithm for solving Sudoku problems in general in polynomial time. The reason for this is that we humans use a sort heuristic-based reasoning where we use some broadly applicable (but not universally applicable) "rules of thumb" to attack these problems in a sort of non-algorithmic way. This approach involves leaving out a lot of irrelevant information and getting straight to the crux of the problem at hand—something that can only be done in specific cases and not in general to NP-hard problems.
So, our best hope, in my opinion, for solving NP-hard problems is to take a more cognitive approach. That is, I think that we should model our algorithms for certain tasks that are well-suited to human brains after the strategies we use to solve them ourselves.
I haven't read Eric Baum's book which you mentioned, but I think that one of his claims is that humans are so successful at thinking because they leave out all the irrelevant possibilities just by the nature of how they evolved—they evolved in such a way that only the important possibilities are addressed in cognitive functioning.
Thus, I think that the algorithm design of the future should take into account traditionally "non-algorithmic" problem-solving strategies like the sort of probabilistic ones humans use in order to perform more efficiently. However, these new "algorithms" will not necessarily be provable to solve a problem, even if they can solve a certain class of problems most of the time. Hence, the way of gaining efficiency in this way will be sacrificing universal applicability in order to simplify the problem.