Problems (tasks?) are an important part of life, science, math, basically everything. Do people study them as mathematical objects? Theorem proving seems close, however, I'm interested more in the taxonomy and ontology of problems and operations on them, like combining several problems or reducing one problem to another.

We, humans, use different heuristics to solve the problems, but how does the problem space look like? What is a structure of the solutions space? How to find a good heuristic for a particular problem? What kind of problems are most prevalent in our universe?

The question is probably a bit vague, I'm sorry. What I want is to reason formally about the problems, problem-solving heuristics, and intelligence as an ability to solve problems.


Part of what you seem to be talking about is either computability theory (also called recursion theory) or complexity theory, depending on whether or not the problems you're interested in are solvable by a computer. If you're primarily interested in solvable problems, complexity theory considers which problems can be used to efficiently solve other problems. Computability theory, by contrast, considers which non-solvable problems we could solve if we had access to the solution to certain other non-solvable problems. In both, there is a notion of combining multiple problems or reducing problems.

On the other hand, there's no good mathematical notion of a "heuristic", so far as I know, simply because "heuristic" is not really a well-defined notion - it just means "general strategy which has generally been right in practice". Numerical analysis considers methods of approximating a solution to a mathematical problem, but I don't think that's what you're looking for.

Questions about the "structure" of the problem space or solution space depends on what you mean by "structure" - both computability and complexity theory have a notion of the structure of the space of problems (neither makes a distinction between the problem and its solution, though).

Finding a heuristic for a problem is computer science's job, though again a numerical analyst might be interested.

Your last question, what kind of problems are most prevalent in our universe, isn't really a theory question at all - it's something that would be determined by experiment. For that, you're looking for something like physics, but don't get your hopes up.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.