67
11
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.
dsaxton
Posted 2016-01-02T04:11:39.003
Reputation: 903
39
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.
D.W.
Posted 2016-01-02T04:11:39.003
Reputation: 128 457
9This 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 – 2016-01-02T08:56:57.263
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 – 2016-01-02T09:29:52.923
3As 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 – 2016-01-02T10:25:11.580
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. – 2016-01-02T22:56:06.930
The question doesn't seem to be phrased in technical language, so I don't think it requires a strictly monotonically decreasing cost function. Consider this: given a cost function $T:\mathbb{N}\to\mathbb{N}$, define $S = {n\ \vert\ \forall m > n\ T(m) < T(n)}$. Then any $T$ for which $S$ is an infinite set (or, heck, a nonempty set) is in keeping with the spirit of the question, I would think. Or at least, I think it is interesting to prove that this broader class of cost functions is also ruled out (which can be done with a slight modification of your answer). – David Z – 2016-01-03T11:47:41.543
@DavidZ, yup! The condition you list is a special case of "there exists $n_0$ such that for all $n \ge n_0$, $T(n)$ is monotonically strictly decreasing", and my argument can be applied directly to show no such function of that form can exist, either. (That's what I was alluding to with "For similar reasons, there is no function that is asymptotically strictly decreasing.", though in retrospect that sentence was pretty obscure.) Are you satisfied by that proof? – D.W. – 2016-01-03T11:58:03.940
@D.W. Sure. Not that I had any trouble coming up with a way to prove the more general statement; I just thought it was interesting and wondered whether you had considered adding it into your answer. (Which you did, so all is set then. Pun intended :-P) – David Z – 2016-01-03T12:08:39.190
@D.W. We are getting into territories of discussing semantics of "getting easier" now. Say, the linear component of the $T$ I propose is for reading and writing output, i.e. the trivial lower bounds. The rest is for actually solving the problem. Then, we could say (imho) that the problems gets easier with big $n$ even though the cost function keeps increasing. I guess what I'm saying is, the classical interpretation of "easy" resp. "easier" may not be the whole truth in the context of this question. (Maybe I should add my own answer?) – Raphael – 2016-01-04T09:48:19.640
1Even 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 – 2016-01-05T14:23:14.753
26
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.
Rick Decker
Posted 2016-01-02T04:11:39.003
Reputation: 14 063
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.)
4@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 – 2016-01-04T09:50:55.243
10
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
Hardware control: many things with hardware get much easier. "Move motor X 1 degree" is hard and/or impossible, and you have to deal with all kinds of things that you wouldn't have to deal with for "move motor X 322 degrees".
Short duration tasks: Say you want item X to be on for (very small amount of time) every second. By increasing the amount of time that X runs, you will need less complex software as well as hardware.
Owen Versteeg
Posted 2016-01-02T04:11:39.003
Reputation: 209
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 – 2016-01-03T09:24:48.420
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 – 2016-01-03T09:26:05.823
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 – 2016-01-05T04:40:34.737
3
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.
Cort Ammon
Posted 2016-01-02T04:11:39.003
Reputation: 2 819
2
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.
Juan Manuel Dato
Posted 2016-01-02T04:11:39.003
Reputation: 49
2Your 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 – 2016-01-02T09:26:30.873
@David, your response is completely incorrect:
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 – 2016-01-02T12:26:11.520
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 – 2016-01-02T13:01:29.950
@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 – 2016-01-02T13:26:10.003
@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 – 2016-01-02T13:37:41.543
@DavidRicherby two things: 1. I cannot see the problem that our structure could not be solved because a "duplicated", 2. If there is a problem, then a requisite is "give us the hints without duplicates". Sorry, but there is no sense in your answer. – Juan Manuel Dato – 2016-01-02T14:23:31.730
@JuanManuelDato I'd appreciate if if you'd stop insulting me. Consider the case where there are just three towns, A, B and C. If I tell you a million times that A must come before B, then tell you that B comes before C, that input necessarily takes longer to process than the input where I just tell you once that A comes before B, simply because it takes longer to read the input. If you insist that the input must contain no duplicates, you've now changed the computation model twice, once by treating part of the input as a parameter and once again by moving to a "promise problem" where [cont.] – David Richerby – 2016-01-02T14:39:19.823
[cont.] the input is assumed to have a particular form and you can't even check that the input is valid within the time complexity that you claim to be able to produce a solution. – David Richerby – 2016-01-02T14:39:56.227
@DavidRicherby First of all I apologize if telling you "there is no sense" is an insult. Moreover, my contributions will desappear soon for sure... In my opinion the asumption of the troll problem is weak because we are not speaking about security, we are speaking about complexity. So, is there a kind of "easy" problem? In that kind of situations be sure that to create a sworm will be easier too, but that is out of scope in my opinion. Thanks for your interest. – Juan Manuel Dato – 2016-01-02T17:12:31.390
@JuanManuelDato OK -- I'm glad "there is no sense" wasn't intended as an insult. Thanks for clearing that up. – David Richerby – 2016-01-02T19:16:22.473
1
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:
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.
RunOrVeith
Posted 2016-01-02T04:11:39.003
Reputation: 219
2This 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 – 2016-01-02T15:21:51.157
0
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.
chris
Posted 2016-01-02T04:11:39.003
Reputation: 111
1This 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 – 2016-01-03T23:38:37.067
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 – 2016-01-04T18:56:06.277
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 – 2016-01-04T19:02:45.830
2"Gets more effective" != "gets easier". – David Richerby – 2016-01-04T19:06:21.490
-1
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).
yemelitc
Posted 2016-01-02T04:11:39.003
Reputation: 42
6Thank 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. – 2016-01-02T07:22:56.407
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 – 2016-01-02T07:52:53.660
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 – 2016-01-03T20:53:39.127
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 – 2016-01-04T04:08:32.080
-1
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.
v vv cvvcv
Posted 2016-01-02T04:11:39.003
Reputation: 7
1These 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 – 2016-01-03T09:18:17.017
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 – 2016-01-03T10:51:51.363
1No, 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 – 2016-01-03T11:26:57.953
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 – 2016-01-04T12:05:36.990
I'm a computer scientist, not a mind-reader. Making your claim precise is your job, not mine. – David Richerby – 2016-01-04T12:20:16.847
I am not asking you to read me mind. I am asking you to understand what I have already written. Maybe I am asking for too much. – v vv cvvcv – 2016-01-06T16:36:14.733
8One 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 – 2016-01-02T09:09:28.107
2@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 – 2016-01-02T09:33:30.670
3Do 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 – 2016-01-02T10:25:28.587
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 – 2016-01-02T10:48:56.073
@amon The question asks for a problem that gets easier as the input gets bigger, not a problem that merely benefits from economies of scale. And, in fact, your problem doesn't benefit from economies of scale. There are two ways to make the input bigger: give more hashes, or give longer hashes. The worst-case $n$-bit input is a single $n$-bit hash, not $n/b$ $b$-bit hashes. – David Richerby – 2016-01-02T11:35:40.150
4To 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 – 2016-01-02T15:51:39.450
1
If you're willing to substitute 'easier' with 'more valuable' then we could talk about the Network Effect / Metcalfe's Law.
– A E – 2016-01-02T19:09:33.500What about problems that take faster to prove they have "no solution" rather than effectively solving them ? I would not "solve itself" but instead show than "there is obviously no solution". – Uriel – 2016-01-02T20:02:23.547
1@DavidRicherby It's O(n + <extremely large constant>/n). – user253751 – 2016-01-03T01:10:22.610
@immibis Traditionally, $n$ is the number of bits in the input. If I give you a single $n$-bit hash, it's going to take time about $2^n$ to get a match. – David Richerby – 2016-01-03T01:36:06.450
@DavidRicherby Not for a fixed hash function? – user253751 – 2016-01-03T02:08:13.863
1I think the most interesting thing you could hope for is an interesting combinatorial problem (e.g., number of graphs on $n$ nodes with some property $P(n)$) which requires you to enumerate graphs for relatively small $n$, but maybe you can prove the answer is $0$ for, say, $n \ge 50$. (Here's a stupid one: $P(n) =$ has less than 50 nodes.) – Kimball – 2016-01-03T05:59:11.187
1@Kimball but then the solution would be simply to count the number of nodes and stop after 50. But then the complexity would grow and then become constant after a certain threshold...Not easier. Moreover I believe that any problem with less than linear worst case is simply trivial and uninteresting. – Bakuriu – 2016-01-03T16:55:26.667
@Bakuriu I wasn't interpreting easier in the sense of complexity theory, but in a practical sense (which was maybe what the OP meant). There are certainly very interesting and mathematical problems which are hard for some small $n$ but easier for larger $n$. A notable one (though not an answer to the OP) is the generalized Poincare conjecture.
– Kimball – 2016-01-03T17:37:11.567I second what @Kimball wrote, and would like to give known results from Ramsey Theory as such examples: The complexity indeed becomes constant after a certain threshold for many such questions, and therefore in many cases much easier than for smaller instances.
– mat – 2016-01-03T23:16:14.230Not a 'computational problem' as such, but some things based in statistics get easier as volume of inputs increases. For instance 'If a Flip a coin N times, what % will be Heads (To be accurate +-10%)', with n=2, you're very unlikely to get it right. With n = 10000 you're very likely to get it right within 10%. – JeffUK – 2016-01-04T13:35:19.477
"It takes time $n$ just to read the $n$ hashes you've been given as input!" – who said you must read all input? If it takes $O(n + HugeC/n)$ it's optimal to read at most $n' = \sqrt(HugeC)$. OK, that bottoms out to a const. But for evil inputs I'll use randomized brute force, and I think for expected time it's beneficial to read progressively more hashes as the brute force goes on failing? [I'm talking fixed-function $n$ distinct hashes problem; assuming hashes are really hard and strong randomness; worst: assuming unbounded O(1) RAM hides a lie!] – Beni Cherniavsky-Paskin – 2016-01-05T14:48:56.523
I cheated: "fixed $b$-bit function $n$ distinct hashes" has no legal inputs for $n>2^b$! Also, brute force can never take more than $HugeC \cdot 2^b$, so at some point there won't be a reason to read more hashes. But imagine a family of $\log n$-wide hash functions with $n/log n$ inputs? Point is, "hit at least one target" does get easier in a strong sense the more targets you're given, and it's not obvious that can't be captured formally. There might be a deep reason this is impossible, but "you must read all input" or "T is integer>0 so can't decrease forever" feel shallow... – Beni Cherniavsky-Paskin – 2016-01-05T16:01:18.397