Wednesday, June 28, 2017

A Proposal for Solving P versus NP Problem

I don't know if this idea for solving P versus NP problem was suggested by anyone before or not:

I think history implies there maybe no general polynomial time algorithm for solving NP-complete problems.
But if there is no single algorithm then how about m algorithms?
Then the question is this: m is finite (P=NP) or infinite (P<>NP) (or this maybe better: P<NP)?

Now imagine that each of those m (heuristic?) algorithms can efficiently solve maybe an infinite number of cases.
But each always leave out an also infinite number of cases.
So the question is, if we keep designing new (heuristic) algorithms for the cases left out by the previous algorithms,
would we need to design an infinite number of algorithms or not?

And if finding the answer theoretically is not possible, cannot we search for it experimentally?

(If all NP-complete problems can be converted to each other (in polynomial time),
and we have lots of different (heuristic) algorithms for each,
is not that mean, we could see all those algorithms as different members of the set of m algorithms we seek?)

Assume N is the number of elements in the input problem for a particular NP-complete problem we chose.
Assume we started with N = 1 and increasing the N one by one.
Assume for each N, we enumerated all possible problem setups (initial conditions)
and tried out each of the (heuristic) algorithms we have (so far) on each of those problem setups.
Imagine we filtered out all problem setups which we could solve efficiently (in polynomial time) by at least 1 (heuristic) algorithm we have.

Obviously if for any N, there are still any setups which we have no algorithm for, that would mean we don't have the full solution (for sure)
and so we need at least one more algorithm to solve those cases.
(So our search would end at that point, unless/until we find the algorithm(s) we need to solve all remaining cases for that N.)

The goal of this experimental search would be to record M (number of algorithms) for each (increasing) N.
And try to find of what is the general trend for M.
(Is it increasing linearly or exponentially or changing some other way we could recognize.)

But isn't it that, heuristic algorithms we have, give us near optimal solutions, not optimal ones for each input case?
(But isn't still there are input cases they give optimal solutions which we could use?)
Even if so we could also accept near optimal solutions (within a certain (error) threshold (percentage)) for each input setup case.
But then the solution (final set of m (heuristic) algorithms) would be a lesser form of solution (for P vs NP problem) even if we find it.

But also if we have the solution (final set of m (heuristic) algorithms where each is polynomial time),
can we really say we have a general polynomial time solution?
For any given setup case of the problem, how we can select any one of m algorithms we have that can solve it (in polynomial time)?
That selection algorithm itself (if exist) is polynomial time or not?

No comments:

Post a Comment