What Is A Problem

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

What is a "Problem"?

When dealing with this in detail we draw a distinction between "Yes/No" questions, and questions with more comprehensive answers. There is a difference. The question "Is this number composite?" is Yes/No and can be answered efficiently. The question "What are its factors?" is not Yes/No, and no efficient algorithm is currently known.

You'd think it would be pretty clear what is meant by "a problem." You ask me a question, I give you an answer, and so on. But the question isn't itself what we think of as "a problem" - each question is an instance of the problem. It's one particular case, one example of the problem.

So we can think of "a problem" as being a collection of (presumably related) questions. What we really want, therefore, is some process that is guaranteed to find, for any given instance, the appropriate answer.

Examples

Note that this is a Yes/No question: Is there a route? If you claim the answer is "Yes" I might ask you for an example, (called a "certificate") but for now, I'm just interested in the "Yes/No" question.

Suppose I give you a map with cities and roads marked on it, and ask if it's possible to plan a route that passes over each road exactly once, and finishes where it started. Perhaps we need to deliver mail, or perhaps we need to grit the roads, or perhaps we're Google and want to update our "Street View" data. This is what we'll call The Gritter Problem.

For the Gritter Problem there is an efficient way to answer every question - there is a simple test to tell us if it's possible or impossible. (It also happens that if it is possible, then there's an effective method to find a route, but that's really beside the point.) But not all questions are easy to answer.

If each city has an even number of roads leading to it, then it can be done. Quick and simple to check - just look at each city, count the roads, and you're done. A map that's 100 times bigger still only takes you 100 times longer - the solution scales simply and easily.

Technically this is the Hamilton Path Problem (HPP), and the Travelling Salesman Problem additionally has lengths or costs associated with the roads. For simplicity I'll refer to the TSP though.

Let's consider an apparently similar question - suppose we want a route that instead of travelling along each road exactly once, visits each city exactly once, the Travelling Salesman Problem. Can you do that as quickly as travelling the roads?

The answer appears to be "No." There is currently no known algorithm that solves the Travelling Salesman Problem in an efficient manner (we explain what that means later, or you can skip ahead and look at "Polynomial Time")

But here's the kicker: no one knows for sure.

Instance Answer 2 [ 2 ] 3 [ 3 ] 4 [ 2, 2 ] 5 [ 5 ] 6 [ 2, 3 ] ... ... 11110 [ 2, 5, 11, 101 ] 11111 [ 41, 271 ] ... ... 53244 [ 2, 2, 3, 3, 3, 17, 29 ]

Another Example

Consider the problem of integer factorisation.

As a problem, this is a set of specific instances, the integers, each of which has an answer - the list of factors. In this case the problem is limited to positive integers from 2 onwards.

Each instance (in this case, each integer) has a natural concept of its size, namely, how many digits. We express the size in terms of the number of bits, binary digits, so the size of the instance n is   

Roughly speaking, twice as many digits means the instance is twice the size.

Technical summary

So a "Problem" is actually a collection of questions. More specifically:

• A problem is a collection of questions
• The questions are called instances of the problem
• Instances have answers
• A solution is an algorithm that given an instance, returns the answer