Are Algorithms created or discovered?

[sethmachine]

Hi,

(if this is in the wrong thread, please move it an appropriate section)

I was curious if someone knew the lower limit on how much "time" or "energy" it would minimally take to come up with an algorithm, where the amount of time/energy spent is proportional to the time complexity of the algorithm.

Hypothesis: It probably takes very little effort to come up with bubble sort, but probably much longer to re-invent the general number field sieve.

Clearly there is some kind of relation, but also some of it is dependent upon the agent's own awareness of mathematical / programming axioms. If I have access to all the "research" up till now, it would probably be more trivial to re-discover any known algorithm, whereas if all I know is elementary arithmetic, I probably will have a harder time coming up with algorithms that were only possible (to humans) because of advances in mathematics/cosi research.

I would be concerned with the tabula rasa--the agent's knowledge is a clean slate and only knows the most basic mathematics / rules about algorithms (must be a finite set of steps, etc.). Is it possible to quantify how long it takes the agent to re-discover an algorithm, and would this information even be useful?

Also, why are certain properties of mathematics or more complex algorithms not intuitive to the simple learner? For example, given the (high school/calculus) definitions of pi, e, and the imaginary number, i, it would be bonkers for me to see this and expect to say "oh wow that makes sense":

e ^ (pi * i) = -1

Yet it's not really a mathematical fact that was invented but it always existed because of the properties and axioms of how those constants are defined, along with the definition of the exponentiation operator (or this my opinion).

So it's also true for algorithms--in order to be efficient they have to take advantage of the structure/properties of what is being manipulated. Binary search works in logarithmic time on a sorted list due to the fact that it is sorted. This is sort of intuitive and even how people look up information in dictionaries, phone books, etc.

But something like the General Number Field Sieve? It's not immediately obvious (to me) how the properties of natural numbers facilitate an algorithm with this time complexity for factorization.

 

[muzzel]

I didnt read your post, but from the title: they are created.
But il read ur post later, im in a rush right now

 

[Menag]

I'd say they are discovered. One would also say that euler discovered the above mentioned identity. These algorithms/identities always existed.

But the actual question in your post is different.
Coming up with a simple algorithm is always very easy. Finding efficient algorithms can be very hard. You often have to find a little trick and it's not always about missing knowledge.

And about the mathematical identity. It isn't created. It really always existed. It's in the nature. All these constants can be defined clearly and it doesn't matter if you call them pi or give them some other name. For example:
exp is the function with the property exp(z) = exp'(z) with exp(0)=1. This definition is unique.
Now one can define e := exp(1) and e^z := exp(z). And pi * i is just half of the period of the complex exponential function. Hence there exists a c with exp(z) = exp(c+z) such that |c| is minimal and unequal to 0.

 

[sethmachine]

So the next part would be, how long does it take an intelligent agent to discover a non-obvious mathematical identity or an efficient algorithm? Does quantifying this in any meaningful way lend any useful insights?

And what do you mean about "tricks?" Must not all algorithms (which are efficient) make use of the structure/properties of the manipulated data? So these tricks should fall out from analyzing the total or accumulated knowledge.

I guess I would want to conduct a search for algorithms and eventually discover the most efficient ones.

 

[muzzel]

I didnt vote for discovered :>

 

[Adiktuz]

most things in this world are discovered... IMHO, there are only a few things that can be considered as "created"

 

[Menag]

So the next part would be, how long does it take an intelligent agent to discover a non-obvious mathematical identity or an efficient algorithm? Does quantifying this in any meaningful way lend any useful insights?

I think these questions are not possible to answer to.

And what do you mean about "tricks?" Must not all algorithms (which are efficient) make use of the structure/properties of the manipulated data? So these tricks should fall out from analyzing the total or accumulated knowledge.

Yes of course they abuse the structure and other properties. But coming up with the idea behind it is the actualy problem. I think we all know how natural powers work. Still most people make a stupid implementation which is only in linear time. Fully understanding a structure doesn't always let you instantly see the most efficient algorithms.
That's what I mean with "You often have to find a little trick and it's not always about missing knowledge.". Same counts for Karazuba-Algorithm. The idea behind it is actually very simple, because the abused structure is well-known. Still coming up with the idea isn't something everyone tends to.

I guess I would want to conduct a search for algorithms and eventually discover the most efficient ones.

 

[Magtheridon96]

So the next part would be, how long does it take an intelligent agent to discover a non-obvious mathematical identity or an efficient algorithm?

6 to 8 weeks

 

[muzzel]

There is no answer to this question. Some algorithms take more time, some take less. Some algorithms are created based on things discovered by luck... etc.

There surely is a correlation between the complexity of an algorithm and the time required for its creation, but there is no quantifiable dependency. Your whole question doesnt make sense.

 

[sethmachine]

I think the problem is I am asking my question to the wrong audience.

But thanks for the discussion

 

[Magtheridon96]

I'd appreciate non sarcastic replies. If you aren't qualified to chime in then don't. Thank you Magtheridon.

A stupid question deserves a stupid answer.

I mean, what kind of answer are you expecting? A duration? A generic "It depends"? An obvious "It doesn't work like that"?

I'm fully qualified to testify, thank you.

 

[Menag]

Then specify your fucking question. What answer do you expect? Do you want us to describe a function depending on the complexity of an algorithm which gives you the time it takes to find it? That's just plain stupid.
Since there are algorithms which are already found and proven that there are no algorithms which are significantly faster. For example Quicksort/Radixsort/Bucketsort/Mergesort. You won't find algorithms with a better time complexity.
It also differes for the problem you have. 4000 years of studying factorization still didn't let us obtain an algorithm in polynomial time, while the euclidean algorithm is actually the first algorithm found for finding the greatest common divisor and fucking old.
This question just can't be answered. Either you take an all-known-guy who obviously already knows these algorithms and therefore doesn't need any time to find them or you take some random well-educated guy who knows maths/computer science and hope that he's going to find the algorithm. It also takes some luck finding an algorithm or proving an identity.
And in the maths world you usually have a conjecture which you then try to prove. At least when it's not a completely new section. And since it is so fucking hard to actually find out things which noone ever heard of the normal exercises for mathematics students are like "Prove the formular xxx" and not "Do some random stuff with this such that it looks nice".

 

[Noobsmoke]

Fact : This thread is pointless as the question is
It's like asking "When the world will end ?"

 

[muzzel]

Actually some people have very profound opinions on that world ending thing and they usually have the importunate habit of showing up at your doorstep to share it with you.

 

[sethmachine]

A stupid question deserves a stupid answer.

I mean, what kind of answer are you expecting? A duration? A generic "It depends"? An obvious "It doesn't work like that"?

I'm fully qualified to testify, thank you.

Thank you. I would appreciate some kind of (formal) arguments or proofs (or even references to relevant research/papers) that demonstrate your point.

Telling me the world is flat and asking me to just believe it just does not seem very satisfying.

 

[Adiktuz]

It really depends on a lot of factors... like what kind of algorithm it is? you cannot really expect a definite answer for a very vague question

 

[Menag]

Just read my answers instead of just talking to the trolls?

 

[Magtheridon96]

Thank you. I would appreciate some kind of (formal) arguments or proofs (or even references to relevant research/papers) that demonstrate your point.

Telling me the world is flat and asking me to just believe it just does not seem very satisfying.

My point was that you're asking a really, really broad question. I wasn't asserting anything that needs to be proved, I'm merely questioning your question.

The process behind discovering an algorithm is mostly through luck. You need to be creative and see the problem you're attempting to solve differently.

Let's say I asked you to design an English phonebook.
With a limited knowledge of data structures, a novice would probably resort to a contiguous array to store information.
Let's say this novice is dealing with a phonebook that has 10 billion phone numbers, and let's assume that one of the requirements is a search function.
In the worst case, with the current setup, a search would take 10 billion iterations. It would be an operation with a time complexity O(n) where n is the number of entries.
The novice needs to be creative and find a way to structure his data differently because the search function would be too slow.
Unfortunately, a lot of novices would start asking the wrong question to solve the problem:
"How can I iterate over the array faster?"
You'll see them resort to crazy assembly language solutions that will only turn out to be marginally faster or even way slower than their C or C++ solutions thanks to modern optimizing compilers.

Some would approach the problem differently and find the right question to ask:
"How can I structure my data differently so I can search through it efficiently?"
Unfortunately, a great chunk of them would resort to crazy solutions like using 26 different arrays to structure the data based on the first letter in the name associated with each phone number entry, you know, one of those "clever" things. They're on the right track at least.

There isn't really a train of thought that allows someone to deduce that the best method of doing this is having the data structured in a DAWG. (Directed Acyclic Word Graph)

It takes creativity to come up with things like this. You have to sit down, think, mess around, doodle, write down mathematical equations and identities and try to diverge from them so you convince yourself that you think you just might know what the fuck you're doing, etc...

 

[peq]

Of course, in general the problem of finding an algorithm cannot be solved automatically. In general it is not even possible to decide whether two algorithms are equivalent, or if an algorithm terminates *

Therefore people consider only a relatively small domain of problems and let computers find algorithms for them. One popular example is SQL, where the user describes the problem in a very high level language and the computer comes up with an algorithm to compute the answer to a query (query planning).