Interesting to note that many people have been able to prove P ≠ NP. Could that be the ultimate solution? We know Dark Matter exists, we just can't see it - that could be similar for the P ≠ NP problem and in the end we may just have to accept that.

Interesting to know that this problem was solved.

Would you please tell me about the immediate consequences of this finding?

Regards,

Nabil BELGASMI.

It hasn't been confirmed as solved.

An answer to the P = NP question would determine whether problems like the subset-sum problem that can be verified in polynomial time can also be solved in polynomial time. If it turned out that P does not equal NP, it would mean that there are problems in NP (such as NP-complete problems) that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

CCCCCC,

P=NP, where N=1, isn't that obvious :)

Elemetary school, such a beautiful period of life, everything is so simple and so easy ...

Dear Konrad,

Since you use the word "advances", I guess you need TECHNIQUES or APPROACHES rather than a simple list of publications, which probably means nothing to you (and to me).

The problem is far from solved, with some experts (namely Lance Fortnow) saying it will need 2 or 3 centuries to be solved, simply because "we don't possess the kind of math needed now".

An approach that seems to have some future is Ketan Mulmuley's program on Geometric Complexity Theory (GCT), which refers to the use of geometric techniques to prove results in Complexity Theory, rather than algebraic proofs (don't mistake this for the study of Computational Geometry). More info can be found at Mulmuley's website http://ramakrishnadas.cs.uchicago.edu/ .

Another attempt that might be promising is boolean circuit lower bounds. There is a number of results in that area that if proven, would directly imply that P is not equal to NP. Unfortunately, the early success of this field was followed by two decades of drought, until Ryan Williams proved an interesting results the previous year, "Non-Uniform ACC Circuit Lower Bounds" . You can find that in his personal homepage http://www.stanford.edu/~rrwill/projects.html .

There are other approaches as well, but from my experience talking with experts, there is a reluctancy to support them as viable.

Barbosa, Uniform Polynomial Time Bounds, and Promises http://arxiv.org/abs/1106.1150

about Vega paper on arxiv "This paper has been withdrawn by the author due to a flaw in the Theorem 5.1

Thank you Harry, and Mr-Moon.

Harry, do you know of any new approaches using Structural Complexity Theory ?

As far as I know, there is not a current attempt to solve P vs NP using only Structural Complexity Theory. Although I am very interested in this particular subsection, I think that either less resistant results should be proven first and used as a stepping stone towards solving P vs NP. Also, keep in mind the amazing network of results under certain hypotheses. Especially in the case that P is not equal to NP, this can be shown by a vast number of different results between other classes. On the opposite way, proving that P is not equal to NP would also strengthen the confidence of some results from conditional to proven without conditions.

To the best of my experience, results are trying very shyly to cover the gap between what we know and what we would like to know (I recommend reading some posts from Godel's Lost Letter , maintained by Dick Lipton and Ken Regan, that phrase is probably more theirs than mine). For example, from the above blog I learned that there was an improvement on separating nondeterministic classes from the equivalent deterministic. See the blog post and a link to the paper:

http://rjlipton.wordpress.com/2011/01/19/we-believe-a-lot-but-can-prove-little/

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2392

Having travelled to FOCS 2010, I also have in print some papers referring to results about complete problems. For example, Andreas Bjorklund has a paper http://arxiv.org/abs/1008.0541 that gives an improved algorithm for Hamiltonial Cycle. A few pages later, Rahul Santhanam appears again http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5670827 with algorithms for solving SAT and QBF. Another recent result that could relate to the P vs NP question is that QIP = PSPACE. http://arxiv.org/abs/0907.4737

Ah yes, the essay by Fortnow. As one gains a degree of familiarity with a problem that seems to have no obvious solution to him or his immediate peers, perhaps it is good to grasp the beliefs of the scientific community, as an indicator of the current status of our progress. The polls conducted by Bill Gasarch ( http://blog.computationalcomplexity.org/2011/06/i-am-conducing-new-poll-on-p-vs-np.html ) are of this kind. The one conducted in 2001 is available, but the 2011 one has not been published yet, as far as I can remember.

However there are examples in the past where the community was on the totally wrong track, think of the effort to axiomatise mathematics for a third of a century that ended with an unexpected result by Godel (see http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#History and http://en.wikipedia.org/wiki/Principia_Mathematica) .

One should also consider the possibility that P vs NP might be independent of ZFC, our usual axiom system ( http://www.scottaaronson.com/papers/pnp.pdf ) or even that it is undecidable in any "reasonable" axiom system (unlikely, but possible).

See also my incomplete paper for the definition of the "crash" in planar graph coloring.

https://www.researchgate.net/publication/260075736_Almost_Uniquely_Chromatic_4-Critical_and_Three_Colorable_Planar_Graphs?ev=prf_pub

Article Almost Uniquely Chromatic 4-Critical and Three Colorable Planar Graphs

My professor told around a year ago, than an indian guy has proved that P is not equal to NP. he has not shared the reference, so I cannot say anything about its authenticity.

I would appreciate if somebody knows about it, than let me know.

Probably one of the more interesting ways people have approached P vs. NP has been hardness of approximation. Instead of looking directly at exact algorithms, one can consider the existence of approximation algorithms. For example, for any positive rational value c, if there exists a c-approximation algorithm for TSP, then P=NP. Also another example, if the makespan problem on unrelated parallel machines has a p-approximation algorithm where p

Abstract only

https://www.academia.edu/10213412/From_the_Proof_of_the_Four_Color_Theorem_to_P_NP

Where would one be able to submit a possible answer ?