Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

When my prof introduced us to the N/NP topics, the first thing he mentioned is input size, which he defines as the number of bytes needed to describe and write a problem's input into a file. Could someone please explain to my why the input size matters to these topics? Thank you.

EDIT: I'm concerned about why this way of measuring size is important, esp. to this P/NP topic. My prof mentioned the pseudo-polynomial running time (of the knapsack problem) which is somewhat relevant to this way of counting input size. I'm not sure how it is connected to the NP picture, mostly because right after redefining input size, he went into reduction examples and there is no mentioning of input size since. And for NP-hard problems, since there is no known way to solve them efficiently, why should we care about input anyway?

share|improve this question
4  
The input size is a measure of the size of a particular instance of the problem being solved. It should be natural to you that it is harder to find a coloring of a graph with 100000000 vertices than one with 3 vertices, and that it will probably take more time and require more memory! –  Mariano Suárez-Alvarez Aug 13 '12 at 22:44
    
Are you concerned about why size matters (in complexity theory)? or why this particular measure of size matters? –  Arthur Fischer Aug 13 '12 at 22:48
2  
Size matters? That's not what I was told... –  Code-Guru Aug 13 '12 at 22:58
    
Do you know that sorting can be done in $O(n\log n)$ time but searching a list for the largest number can be done faster, in $O(n)$ time? If so, what do you suppose $n$ is? –  MJD Aug 14 '12 at 1:45
    
@MarianoSuárez-Alvarez Regarding: "It should be natural [..]" I agree of course; the larger the inputs, the more the steps in finding the solution. But do you know if there is a theorem that proves this trivial (or obvious) fact? –  user2468 Aug 14 '12 at 1:53

2 Answers 2

up vote 1 down vote accepted

The simplistic is answer is that complexity classes are defined in terms of the size of the input (of course there are other ways, via descriptive complexity and so on, but I'll stick to the basics). So introducing the size of the input is essential to defining the classes.

Naturally the question then becomes why define these things in terms of the size of the input? The whole raison d'être for these classes is to work out how much of a resource we need to expend to solve a problem. Perhaps we're interested in how much time it takes, or how much space, or some other resource, but above all we want to know what's possible and how much it'll cost us. Like the other comments and answer have said, it's pretty reasonable to expect that giving a bigger input will consume more of the resource we're interested in. Moreover, it's kind of uninteresting to see how much time/space/etc. it takes to solve a single instance - what we want is a classification that tells us how much we need to expend to solve any possible instance, without just trying it and seeing (imagine checking how long it took to solve a particularly hard instance of a particularly hard problem and finding out it took 10 years, or worse, the lifetime of the universe).

So then of course we need some way of relating the instance to the amount of resources needed to solve it. The first natural measure is the size of the instance - if you give me a bigger instance, it takes more time/space/etc.

share|improve this answer
    
Thank you. Input size matters to problems in P. But for NP-hard ones, since there is no known way to solve it efficiently, why should we care about input anyway? –  cody Aug 14 '12 at 2:37
    
There's two bits to my reply, but it takes a few too many characters, so I'll split it over two comments. The things in $NP$ are still the things that can be solved efficiently on a non-deterministic machine (as distinct from problems that are in $NEXP$ but outside $NP$, where we need possibly up to exponential non-deterministic time, so the resources used as a function of the size of the input still gives important information. –  Luke Mathieson Aug 14 '12 at 3:13
    
On top of this, the classical split where we call $P$ "efficient" and everything outside $P$ "infeasible" is not really an accurate portrayal of reality, there are $NP$-hard problems that have excellent, practical algorithms (via parameterized complexity, exact exponential algorithmics, approximation, randomisation etc.) and problems in $P$ that have fairly miserable algorithms. In both cases, we still use the size of the input as the basic measure when talking about the complexity, e.g. we can solve SAT in time bounded by roughly $2^{n}$ (yes, there's some detail missing there). –  Luke Mathieson Aug 14 '12 at 3:16

Let's look at a simple example:

Sort the following numbers in ascending order:

8
485
314
2
146

Now sort the following numbers in ascending order:

72
277
304
326
287
152
205
68
444
250
70
490
384
81
180
126
397
402
259
295

I'm willing to bet that you were easily able to sort the first set of numbers in your head but the second list takes you quite a bit more time.

Okay, so sorting is actually a problem in P, not just NP. A big part of studying complexity of algorithms is determining how the time to solve a problem is affected as input sizes get larger and larger.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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