You are currently not logged in.
To change this, fill in the following fields:
Who can read this page?
You have been granted an edit lock on this page
until Tue Dec 10 07:07:18 2019.
to finish editing.
Who can edit this page?
Prev: Introduction / Next: Time Complexity ---- ! What is a "Problem"? [[[>50 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 [[[>50 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. COLUMN_START^ 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. COLUMN_SPLIT^ [[[ 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. ]]] COLUMN_END [[[>50 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. ---- [[[>50 | 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 EQN:\log_2(n). 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 In the case of integer factoring there is a trivial algorithm: trial division. The problem is that this is very slow in bad cases. This leads us to talk about the "Time Complexity" of a problem, but which we mean how the time of solution grows (in the worst case) as a function of the size of the problem. ---- Prev: Introduction / Next: Time Complexity