Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size? I doubt any practical problems are like this, but maybe we can invent a degenerate problem that has this property. For instance, perhaps it begins to "solve itself" as it gets larger, or behaves in some other bizarre way.

share|cite|improve this question
6  
One real problem with this property that comes to mind is unsalted password hash cracking when it is formulated like “given n hashes, crack at least one hash”. Since cracking speed would scale linearly with n, running time would be proportional to 1/n – except that we can't actually assign a definitive time since cracking is stochastic and does not have a constant upper bound on time. – amon Jan 2 at 9:09
1  
@amon The running time doesn't scale like $1/n$. It takes time $n$ just to read the $n$ hashes you've been given as input! – David Richerby Jan 2 at 9:33
3  
Do you mean easier in absolute or relative terms? Which cost measures do you permit? Do you require strictly decreasing cost, or is non-increasing (from some point on) enough? – Raphael Jan 2 at 10:25
2  
@DavidRicherby In this example, it is legitimate to ignore the cost of reading the input as long as I don't make any statement about the absolute cost. Instead, the speed increases linearly with the input. Therefore, n•T(1)>T(n) even when considering the cost of reading the input. I.e. for this problem it is easier to solve a large input at once rather than splitting up the input, even though the problem is divisible. I am not saying that T(n)>T(n+1) for all n. – amon Jan 2 at 10:48
4  
To everybody who wants to post yet another answer of the form, "Some problem where the input is a question plus a big bunch of hints about the answer": This does not work. The hardest inputs of length $n$ are the ones where you use all $n$ bits to ask the question and give no hints. The fact that it's easy to deal with short questions with a lot of hints does not mean the worst-case running time is good. – David Richerby Jan 2 at 15:51

10 Answers 10

up vote 36 down vote accepted

No, it's not possible: at least, not in an asymptotic sense, where you require the problem to keep getting strictly easier, forever, as $n \to \infty$.

Let $T(n)$ be the best possible running time for solving such a problem, where $n$ is the size of the input. Note that the running time is a count of the number of instructions executed by the algorithm, so it has to be a non-negative integer. In other words, $T(n) \in \mathbb{N}$ for all $n$. Now if we consider a function $T: \mathbb{N} \to \mathbb{N}$, we see there is no such function that is strictly monotonically decreasing. (Whatever $T(0)$ is, it has to be finite, say $T(0)=c$; but then since $T$ is monotonically strictly decreasing, $T(c) \le 0$ and $T(c+1) \le -1$, which is impossible.) For similar reasons, there is no function that is asymptotically strictly decreasing: we can similarly prove that there's no running time function $T(n)$ where there exists $n_0$ such that for all $n \ge n_0$, $T(n)$ is monotonically strictly decreasing (any such function would have to become eventually negative).

So, such a problem cannot exist, for the simple reason that running times have to be non-negative integers.


Note that this answer covers only deterministic algorithms (i.e., worst-case running time). It doesn't rule out the possibility of randomized algorithms whose expected running time is strictly monotonically decreasing, forever. I don't know whether it's possible for such an algorithm to exist. I thank Beni Cherniavsky-Paskin for this observation.

share|cite|improve this answer
8  
This is a nice proof, but I disagree with the premise. Instead of asking for a strictly monotonically decreasing runtime, the question might more reasonably be requiring a function where there exists an a, b with a<b so that T(a)>T(b), i.e. its non-strictly monotonically decreasing. Then, it's of course possible to find suitable integer functions. But why integers? I was under the impression that running time denoted a time, not an instruction count (except of course for Turing machines), and that the T expression could use the non-integer operations like log() or non-integer exponents. – amon Jan 2 at 8:56
2  
@amon "running time denoted a time, not an instruction count" Absolutely not. Running time is always an instruction count. Anything else would be impossible to reason about as it would depend on infeasibly many implementation details. – David Richerby Jan 2 at 9:29
3  
As vague as the question is, I don't see how it excludes a cost function of, say, $T(n) = n^2 \cdot (1+\epsilon)^{-n} + n$. Now, $T(n) \sim n$ but $T(n) \approx n^2$ for "small" $n$, so the problem "gets easier", relatively speaking. (Absolute costs grow asymptotically, of course). – Raphael Jan 2 at 10:25
2  
@Raphael, $T(n) \sim n$ is not a problem getting easier: $T(n)$ gets larger as $n$ gets larger, so the problem gets harder as $n$ gets larger, once $n$ is large enough. I did state in the first sentence of my answer that no problem can keep getting easier forever. Of course, a problem can get easier for a little while ($T(n)$ can be decreasing for $n \le c$, say), but but it can't keep getting easier forever. – D.W. Jan 2 at 22:56
1  
Even with integer times, for a randomized algorithm the expected time (or any other measure of the distribution) can be fractional, and could gradually approach some constant from above. [This doesn't mean such problems actually exist, only that the "no such function $T$ exists" argument is insufficient.] – Beni Cherniavsky-Paskin Jan 5 at 14:23

Although it's not quite an answer to your question, the Boyer-Moore string search algorithm comes close. As Robert Moore says on his web page about the algorithm,

Our algorithm has the peculiar property that, roughly speaking, the longer the pattern is, the faster the algorithm goes.

In other words, generally speaking the algorithm searches for an instance of a target string in a source string and for a fixed source string, the longer the target string is, the faster the algorithm runs.

share|cite|improve this answer
10  
Arguably, the pattern isn't the size of the problem but instead the length of the string being searched is. As in David Richerby's comment above, I would argue that the length of the pattern is more of a hint about how to solve the problem (got about searching the string) than the problem itself (seeing if a pattern matches a string of a particular length.) – Kevin Jan 3 at 2:08
3  
@Kevin The statement suggests that searching a pattern of length $\sqrt{n}$ in a length $n$ text is faster than searching a pattern of length $\log n$. Looking at such fixed-relation inputs (i.e. pairs of strings), I think Rick has given a suitable answer to the question (if not in the classical, asymptotic sense). – Raphael Jan 4 at 9:50

Clearly, from a pure mathematical, purely CS algorithm viewpoint this is impossible. But in fact there are several real-world examples of when scaling up your project makes it easier, many which are not intuitive to end-users.

Directions: the longer your directions get, they can sometimes get easier. For example, if I want Google Maps to give me directions for going west 3000 miles, I could drive to the West Coast -- and would get cross-country driving instructions. But if I wanted to go 6000 miles west, I would end up with significantly simpler instructions: get on a plane from NYC to Hokkaido. Giving me a cross-country route that incorporates traffic, roads, weather, etc. is rather difficult algorithmically, but telling me to get on a plane and looking up flights in a database is comparatively significantly simpler. ASCII graph of difficulty vs distance:

           |     /
           |    /
Difficulty |   /                  ____-------
           |  /           ____----
           | /    ____----
            ---------------------------------
                       Distance

Rendering: say I want a render of one face and a rendering of 1000 faces; this is for a billboard ad so both final images must be 10000px by 5000px. Rendering one face realistically would be hard -- at the resolution of several thousand pixels across you have to use really powerful machines -- but for the crowd of 1000 faces each face need only be ten pixels across, and can easily be cloned! I could probably render 1000 faces on my laptop, but rendering a realistic face 10000px across would take a very long time and powerful machines. ASCII graph of difficulty vs. objects rendered, showing how difficulty of rendering n objects to an image of a set size drops off quickly but then returns slowly:

           | -    
           |- -                     _________
Difficulty |   --      ______-------            
           |     ------      
           |       
            ---------------------------------
                        Objects
share|cite|improve this answer
    
In your "directions" example, please state exactly what is the computational problem and what is the instance. It's not at all clear to me that your 6k miles example is a larger instance or just an example of an easy part of something (e.g., if I give you a large graph connected graph plus one isolated vertex, asking for shortest paths in general is "difficult" but asking for a shortest path from the isolated vertex to anywhere is trivial). Again, for your rendering example, what is the actual computational problem? What is the instance against which you're measuring complexity? – David Richerby Jan 3 at 9:24
    
The rendering example doesn't seem to be instances of the same problem: the first one is rendering a single image; the second one is rendering many small images and then pasting multiple copies of those images into some area. – David Richerby Jan 3 at 9:26
    
I think wrt to travel the parameters would be the name of the 2 cities and n would be the number of characters to encode them. – emory Jan 5 at 4:40

There are cases. They are the cases where the success criteria is a function of the data, rather than trying to find a single answer. For example, statistical processes whose results are phrased with confidence intervals can become easier.

One particular case I'm thinking of is problems which have a transition from discrete behaviors to continuous behaviors, like fluid flows. Solving the small problem to within a degree of error can involve modeling all of the discrete interactions, which may call for a supercomputer. The continuous behaviors often permit simplifications without yielding results outside of a related error bound.

share|cite|improve this answer

The question is interesting and USEFUL, because our philosophy in informatics is to solve problems the more we read the more dificult is. But, in fact, the MOST of the problems that are presented in the typical way (difficult) can be easily represented in the "easy" way; even knowing the response of D.W (which is in a wrong considering that easy does not mean faster, means "less slow"; so you do not have to find negative times, you hace to find asymptotic time).

The trick to find one is putting the part of the solution like hints as an entry, and considering the entry of the problem like a constant parameter.

Example: What is the longest way in car between London and Paris avoiding to visit twice a French and a British town and not visiting other country? considerin, you have to go to Birmingham before Ashford, Orleans before Versailles, La Rochelle before Limoge, etc...

It is clear that this problem with long entries will be easier that with short ones.

Example of use: Imagine a playgame managed by the machine, and the IA of the computer have to determine if he has to explore more in the play to find more hints or else, if now is time to deduce what is the best decision to assume.

share|cite|improve this answer
2  
Your example doesn't work. Instances that are large because they have so many hints that the hints determine a linear order of the graph's vertices are indeed easy. However, instances that are large because they give a large graph with almost no hints are just as hard as the ordinary Hamiltonian path problem. Thus, the worst-case running time of any algorithm that solves this problem is going to be at least as bad as the worst-case running time of the best algorithm for Hamiltonian path, which doesn't seem to be "super easy". – David Richerby Jan 2 at 9:26
    
@David, your response is completely incorrect: 1. The entry is not a graph: the large graph is a PARAMETER. So the hamiltonian problem is converted to a constant (very large, but a constant). 2. The entry is the solution of the problem, so: if greater, you are offering a combinatorial explossion of hints. An entry of one hint gives a help, two hints the double, three hints will be close to 4 twices..., because you are eliminating possible solutions. So, this was not a Hamiltonian, this is a solution from an especific graph and the problem is WHAT to do with parts of the solutions. – Juan Manuel Dato Jan 2 at 12:26
    
I think your argument is interesting as larger instances are "easier" in some sense, but I think the answer to the original question is ultimately "no". Since the graph is finite, there are thus only finitely many possible hints. Therefore every instance can be solved in constant time (for instance, using a lookup table). Even though larger instances are (intuitively) easier in the (asymptotic) computer science view all instances are equally hard (solvable in constant time). – Tom van der Zanden Jan 2 at 13:01
    
@Tom, I agree your consideration about the complexity will be constant, but the problem is how we are accepting the new hints: if with our philosophy of calculating the long entry is not better than a short entry, then we have to change our philosophy - because that is a fact: long entries implies easier problems. So we cannot work in that way... I would recommend my book, but I have no reputation... – Juan Manuel Dato Jan 2 at 13:26
    
@TomvanderZanden Actually, it can't be solved in constant time because the list of "hints" might contain duplicates. It requires something like time $n\log n$ to deduplicate before you can do the table look-up. So, guess what? Solving bigger instances is still harder. – David Richerby Jan 2 at 13:37

Consider a program that takes as input what you know about a password and then tries to crack it. I think this does what you want. For example:

  • No input-> Brute force crack over all symbols and a word of any length
  • Length of password -> Brute force all symbols in a word of that length
  • Contained symbols -> Shrinks list of symbols to check
  • ...
  • Contained Symbols including multiple occurrences and length -> Only compute permutations
  • All symbols in correct order -> basically solved itself

I should add that this is a trick, since the problem stated like this is inverse to to input size. You could leave out one layer of abstraction and say that the input size is large for no input (check all symbols and lengths of words) and small if you enter the correct password in the beginning.

So it all comes down on how much abstraction you allow.

share|cite|improve this answer
2  
This doesn't work. First, it's not a well-defined computational problem: suppose your input is just "The password has 8 characters" -- that doesn't uniquely determine any password. Second, suppose you make it well-defined by including a hash and asking for any password that matches the hash. In this case, the hardest instances are the ones of the form "The hash is: [$b$-bit hash]" with no extra information. These instances don't get easier to solve as the input length increases: they get exponentially harder. – David Richerby Jan 2 at 15:21

If we take Sudoku or Nonogram, the larger the input (number of given cells), the easier it gets.
Maybe not this kind of growth you had in mind. So for any system with constraints, when you give enough, you have to do computation, the more you give until system is overspecified, it gets simpler.

But for more common problems, that have exponential, loglinear, polynomial runtimes this is hard - you would have to make computation like 1/n type, so maybe flow checking, when you increase number of edges in fixed vertices - your DFS works faster.

But in general case, when you do not have fixed parameter, it would mean that bigger instance takes lower number of steps. Since it does not ommit any part of input, it gives contradiction that computation is optimal. Another reason is that at infinity, problem would be solved.

This would be not reasonable and unstrict, but let us imagine that you have to enumerate all natural numbers, and you can provide "half of them", weird assumption, that you can provide half of the infinite sequence, but this is image of what kind of problem you need.

No can do.

It is the same argument as Rick Decker gave about easing computation. It was not clear enough how exactly easier problem is getting. So I perfectly understand your comments, but none if them contradicts my answer.

But is clear that some users here are negatively biased towards my answers.

share|cite|improve this answer
3  
Solving Sudoku on a $n \times n$ grid requires at least $n^2$ time (just to read the input), so it can't keep getting easier forever -- eventually the running time has to grow (get harder) at least quadratically.... Put another way, the running time for Sudoku is $\Omega(n^2)$, so it can't keep getting easier forever. – D.W. Jan 2 at 5:45
1  
Moreover, if the input is a partially filled Sudoku, the problem is NPC. – Juho Jan 2 at 9:25
    
hey, I do not understand your comments. Nonogram is exponential, SAT equiv, sudoku is hard, but the solvable minimum is 14 cells, if you increase it to say 40, problem gets easier. @D.W. I saw, you were first with answer ;) And I explicitly stated that for fixed size, so with increase of k not n. This differ from increasing grid size... But this is different from e.g. giving more elements to get sorted, and it was not that obvious if this is rejected path – EvilJS Jan 2 at 17:45
1  
@EvilJS The solvable minimum for a $9\times 9$ Sudoku is 14. But if you're only interested in $9\times 9$ Sudokus, the problem is solvable in constant time. – David Richerby Jan 3 at 10:45
    
Well, if you're restricting to $9\times 9$, it can't possibly get easier as the input gets larger because you still have to read the input, which is getting bigger but, once you've read the input, you can pick out the answer in constant time. The only computational task that isn't table look-up is parsing the input. – David Richerby Jan 3 at 15:19

As a matter of fact, I do have a problem that gets smaller as the data increases. One of my application records attributes of a particular product, say cheese. Attributes are for instance CheeseType, Brand, Country, Area, MilkType, etc. Every month or so, I get a list of new cheeses that came into the market during that time, along with their attributes. Now, these attributes are typed by hand by a group of humans. Some make typos, or just don't know the value for all attributes.

When you make a search in my database, I try to predict from statistics what the cheese tastes like, based on these attributes. What happens, is that for each attribute, I end up with a range of values ; some are valid some are invalid. Eliminating or correcting these invalid ones is only possible if I have enough data. It's about making the difference between real values and noise, without eliminating rare but valid values.

As you can imagine, with low volume, the noise is too important to fix things properly. If you have 5 instances of Cheddar, 1 of Brie , 1 of Bri, and 1 of Chedar, how do I tell which is correct and which is a typo? With more volume, the typos tend to keep very low, but the rare values get a few crucial increments, making them escape from the noise (backed by experience). In this case, I could imagine 50000 Cheddar, 3000 Brie, 5 Bri, 15 Chedar, for instance.

So yes, some problems solve themselves eventually, when you have enough data.

share|cite|improve this answer
1  
This fails for the usual reason. A large input might be one in which people tell you about many different types of cheese, rather than one in which they tell you about a few kinds of cheese but some of them mis-spell it. Also, it's not clear that "easier" is supposed to be interpreted as "allow higher confidence in the result". – David Richerby Jan 3 at 23:38
    
This is a real-life problem (I have had it twice already), that cannot be solved with low amount of data. It can, and it even gets easier to tell apart, good values from wrong ones, as volume gets high. It has the merit of answering the question "Are there any problems that get easier as they increase in size?" It doesn't matter how many types of cheeses come up, eventually, with enough volume, they will have more "hits" than the typos. This is cs.stackexchange, not maths, so problems are different, and solving them sometimes is simply about having higher confidence in the results. – chris Jan 4 at 18:56
    
Isn't this also kind of the premise of the TV show Numbers? Or at least some episodes - I know I specifically recall one scene where the maths guy remarks that the algorithm he's using to solve the problem at hand gets more effective with a larger dataset. – Dan Henderson Jan 4 at 19:02
1  
"Gets more effective" != "gets easier". – David Richerby Jan 4 at 19:06

Consider the NP-complete problem 3-SAT. If you keep augmenting the problem by providing inputs of the form x_i = true/false, you either end up converting the individual disjunctions into two-variable clauses, thereby creating a 2-SAT problem which is decidedly P, or you simply end up getting a true/false answer.

For the case where there is redundancy in the x_i = true/false inputs (same input provided a lot of times, or contradictory inputs) you can easily sort the inputs and either ignore the redundant values, or report an error if the values contradict.

In any case, I think this represents a 'realistic' problem that gets easier to solve as the number of inputs grows. The 'easier' aspect is in converting an NP-complete problem to a P problem. You can still game the system by providing ridiculous inputs such that just the sorting would take longer than brute forcing the problem.

Now, a really cool scenario would be if we are willing to accept T(0) (utilizing D.W.'s notation in the answer above) can be infinite. For example, T(0) could be equivalent to solving Turing's Halting Problem. If we could devise a problem such that adding more inputs converts it into a solvable problem, we have struck gold. Note that it is not enough to convert it into a solvable problem asymptotically - because that is just as bad as brute forcing the problem.

share|cite|improve this answer
1  
These particular inputs get easier. However, when you consider all possible inputs 3SAT in general gets significantly harder as you add more clauses: the hard inputs are the ones without these "hint" clauses. If you're disallowing general inputs, you need to state exactly what inputs you're allowing. – David Richerby Jan 3 at 9:18
    
First off: we are in agreement that adding more inputs can increase the running time. I say essentially the same thing above. Second, I clearly say we are taking an existing 3-SAT and adding only inputs of the form x_i = true/false. I think this is clear enough and I don't need to make any further clarifications. I think you are taking the trouble to form the most misconstrued interpretation of what I have written. Please don't trouble yourself. – v vv cvvcv Jan 3 at 10:51
1  
No, seriously. What computational problem are you solving? A computational problem is deciding the membership of a set of strings (let's say a set of formulas to avoid annoyances about coding). What is the set of formulas for which you're claiming that deciding whether a long formula is in the set is easier than deciding that a short formula is in the set? As soon as you try to make this precise, I'm pretty sure your claim will fall apart. – David Richerby Jan 3 at 11:26
    
Can you please make explicit your understanding of 'my claim'? As soon as you try to make this precise, I'm pretty sure you will stop wasting internet bandwidth. – v vv cvvcv Jan 4 at 12:05
    
I'm a computer scientist, not a mind-reader. Making your claim precise is your job, not mine. – David Richerby Jan 4 at 12:20

The question asks: "is it possible to have a problem that actually gets easier as the inputs grow in size?" What if the inputs are resources to be used by the algorithm to work on a job. It is common knowledge that the more the resources the better. Below is an example, in which the more there are employees the better.

1) You are given two inputs:
i) The number of employees in an industry. This is a natural number and is the main input $n$.
ii) Information about the industry. There are $t$ tasks to be done by the workers, labeled A, B, C, D... There are $p$ places that connect the tasks enabling the employees to switch between tasks. They are labeled 0, 1, 2, 3... The information given is a simple directed graph made up of routes, for example: A-1, 1-2, 2-B, C-3... For simplicity each route has a cost of 1.

2) Problem:
Starting from the first tasks A, and with $n$ employees, you are to find an optimal strategy for the employees to use in order to visit all the tasks. Tasks can be visited more than once. Recall that you cannot switch between tasks unless you find a path between them. The path from task A to B is independent of that from B to A.

3) Output:
The output is the paths between tasks to be taken by the employees. Each path is associated with the number of employees taking it. For example:

A to B with $n1$ employees (a forward path)
A to C with $n2$ employees (a forward path)
B to D with $n3$ employees (a forward path)
D to B with $n4$ employees (a reversed path)
B to E with $n5$ employees (a forward path)

4) Possible solution:
One possible solution is to first compute the shortest path to the closest nodes from A. This will be a forward path. Then recursively compute the forward path for each visited tasks. The result is a tree. For example:

          A
      B      C
    D   E

Now is the time to determine how the employees are going to traverse the tree so to visit the tasks. Starting from task A with $n$ employees, $n1$ are sent to the left subtree and $n2$ are sent to the right subtree. If $n2 \neq 0$ then none from the left subtree will ever need to go to the right subtree.

For $n=\infty$ the employees will all just move forward. For $n = 1$ the employee will have to use reverse paths in order to visit other tasks. For D to B for example the algorithm will compute that shortest path. This is extra computation. Why not directly compute a shortest path from D to E?! Fine, hopefully that is still extra computation.

But of course computation time will not decrease infinitely (by the way for $n$ too large it will lead to poor resource management and stuff).

share|cite|improve this answer
6  
Thank you for sharing your thoughts. Normally in computer science an algorithm is understood to accept a sequence of bits as its input, and output another sequence of bits. With that standard understanding, I don't see how this answer can make sense. If you have a different notion of algorithm in mind, I think it would help if you edited the question to describe what you mean by algorithm (since it sounds like you're not using the term in a way that corresponds to standard usage of the term, as I understand it). – D.W. Jan 2 at 7:22
    
The input can simply be a number (the number of resources). This will affect the number of extra computation the algorithm will have to go through. I will edit the answer to provide a more concrete example. – yemelitc Jan 2 at 7:52
    
Thanks for your edit -- that makes it much clearer. I now see that you're not confusing the cost of computing the solution with the cost of executing it as I originally thought. But now we're in the usual situation. First, it takes at least linear time to read the input. Second, the hard instances aren't the ones where you give a small tree and a gazillion people but where you give a large tree and relatively few people. (E.g., if you allow me a million bits, I'll choose a tree with about a thousand vertices and give you five people, not a tree with five vertices and a thousand people.) – David Richerby Jan 3 at 20:53
    
I agree. It seems we all ended up quite critical about it, unlike what the original question tempted us to! But hopefully you get my idea of 'input as a resource': no matter how large the work, the more people the better. Still in an asymptotic sense you are definitely right, I should just blame it on non-negative integers. – yemelitc Jan 4 at 4:08

protected by David Richerby Jan 3 at 23:39

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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