Posts Tagged ‘algorithms’
Not P==NP for now..
February 28, 2011 | 
Author Some time ago (January 19, 2011), Vladimir Romanov announced that he had found a polynomial time solution for the 3-SAT NP-Complete problem. As I mentioned on the first related post, if this was true it would immediately suggest that P==NP.. A nice article about what would be the implications of this equality can be found in Wikipedia.
The time for such a proof (or the opposite one, which is consider to be more probable) has not come yet. Yesterday, with a comment to his blog, Vladimir Romanov announced that there is a problem with the solution that need to be corrected:
Thank you for your attention to my work. You’d better suspend your investigations.
A shortcoming possibly exists in the filtration procedure which requires an amendment.Best regards,
V. R.
Parallelizing simple algorithms series
Fibonacci Spiral
In the following weeks, I will try to write some posts about parallelizing simple algorithms with the Erlang programming language. The main motivation for executing program instructions in parallel is to complete the computation faster than the sequential equivalent solution. As it is used, when someone wants to present the “parallelization power” of a programming language/model, the Fibonacci numbers are used. So, following this conversion, my first post will be about parallelizing the calculation of the Fibonacci integer sequence.
Read the rest of this entry »
Posted in Parallel Programming | 
Tags: algorithms, erlang, parallelism, programming, series | 
No Comments »
3-SAT polynomial time solution? If true then P==NP
Complexity classes
One of the biggest questions in the CS always was (is) if P==NP, or P!=NP.
I just read a post announcing an article called “Non-Orthodox Combinatorial Models Based on Discordant Structures” by the author V. F. Romanov (http://arxiv.org/abs/1011.3944).
According to the author:
The article presents a constructive proof of effective resolvability of 3-SAT problem, accompanied by description of a polynomial algorithm created for the named purpose.
If this statement is correct, and the algorithm really solves the 3-SAT problem in polynomial time, then P==NP (since 3-SAT is NP-complete). Although the article, in my opinion, looks too draft for such an important topic, if it will be proven correct, one of the biggest findings in CS will be unveiled.
Lets see..