Archive for January 20, 2011
3-SAT polynomial time solution? If true then P==NP
January 20, 2011 | 
Author 
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..
Posted in 
Tags: 
FPGA as a processor?
I just read an article about some research being done on University of Glasgow. Researchers placed/programmed (more than) 1000-cores on an FPGA (about FPGA). Each core is supposed to have each own dedicated memory (it is not a technical article, so not many technical details were given). According to the article:
The researchers then used the chip to process an algorithm which is central to the MPEG movie format – used in YouTube videos – at a speed of five gigabytes per second: around 20 times faster than current top-end desktop computers.
You can read the article here.