-1

when someone finds other solution or algorithm for math or computer science problems how he/she could understand the solution which he/she finds is the best or not base on Time complexity? (maybe the algorithm is sequential or in parallel)

Mehdi bayat
  • 199
  • 2
  • 13
  • Possible duplicate of [How to find time complexity of an algorithm](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – GSerg Feb 02 '17 at 20:31
  • No,my problem is how could find best algorithm exist until now for a special problem in math or computer science and what is its complexity. for example if i find a solution for sum of n big numbers and present a new algorithm for that how could i find is it the best algorithm or not? – Mehdi bayat Feb 02 '17 at 20:40

1 Answers1

0

TL; DR: this is done through thorough mathematical proving and review of existing algorithms. How to evaluate complexity is a different topic that was discussed numerous times here. Not that this answer could surprise you anyhow, but... That's life. Proof is below.

From what I understood, you basically want an algorithm that for any problem will find out if discovered solution is best for it or not. Let's do some math.

F(P, S) -> bool, where P is problem, and S is solution, and it returns Boolean value whether S is the best solution for P or not. Let's also assume that this algorithm somehow knows the set of existing solutions for the problem P. Comparing a new solution to every old one takes a bit of time - you need to evaluate the complexity(memory and time-wise). Let's say that you can find the complexity of a given solution with the complexity of O(S). Then, to compare two of them, you will need to waste O(2 * S) => O(S) units of time(polynomial).

So, if the algorithm knows the set of solutions, the complexity of such metaalgorithm is somewhere near O(K * S), where K is a number of solutions. That seems polynomial.

Now let's throw away the impossible(as no algorithm knows everything), and drop the assumption of a known set. K now becomes a number of nearly any set of actions that can bring to the solution or not! K grows exponentially with the number of actions(K = e^x). Total complexity: O(S * e^x) = O(e^x). 

NP-complete problem definition: Problem is solved by non-deterministic Turing machine, which means there is an algorithm to check if something is a solution to the problem, but no algorithm to find that solution, except for brute-forcing them all.

That task you've given us fits pretty nice. Even more, you've got to brute-force it for eternity, because there's infinite amount of action combinations. =)

Pretty close to the given task.

Community
  • 1
  • 1
Leontyev Georgiy
  • 1,295
  • 11
  • 24
  • thanks for attention. you are very good in mathematics. – Mehdi bayat Feb 02 '17 at 21:33
  • Not a problem :-D I actually had fun writing it :) – Leontyev Georgiy Feb 02 '17 at 21:34
  • I think it's a really great answer. I would love to see more mathematical proofs here for other problems and algorithms. – Cilenco Feb 02 '17 at 21:41
  • @Cilenco Well, this answer doesn't pretend to be within strict rules of math theorem proving. It's all thoughts, pretty much. At least, a fast attempt to write something similar to halting problem's unsolvability proof(it is 2 lines long and very mathematically beautiful) failed :( – Leontyev Georgiy Feb 02 '17 at 22:15