May 31 2013

P = NP (!?)

Tag: 01,Computing, Signs and Reasoning,Informática TeóricaJoaquim Anguas @ 3:02 pm

A Polynomial Time Algorithm for the Hamilton Circuit Problem
Xinwen Jiang
(Submitted on 26 May 2013)

In this paper, we introduce a so-called Multistage graph Simple Path (MSP) problem and show that the Hamilton Circuit (HC) problem can be polynomially reducible to the MSP problem. To solve the MSP problem, we propose a polynomial algorithm and prove its NP-completeness. Our result implies NP=P.

Subjects: Computational Complexity (cs.CC)
Cite as: arXiv:1305.5976 [cs.CC]
(or arXiv:1305.5976v1 [cs.CC] for this version)
Submission history
From: Xinwen Jiang [view email]
[v1] Sun, 26 May 2013 00:40:00 GMT (1363kb)


So, P=NP or not?

We also need a creditable algorithm to tell us if the generated instance contains a simple path. Hence our testing system has three parts: the instance generator, the backtracking algorithm as a benchmark and Z-H algorithm. Until now, since 2010.10.06, more than 52 millions of instances have been generated randomly, each of which has 100 vertices. Some instances contain a simple path while others (it is the majority in all the generated instances) do not. All the results show that our polynomial time algorithm can get the same answer as the backtracking algorithm does. No exception.

Nice try guys, keep it up.

Mar 22 2012

Put Alan Turing on the £10 note!

Tag: 01,Informática TeóricaJoaquim Anguas @ 12:00 am

Alan TuringSign here.
Via BoingBoing.

Sep 11 2009

“You deserved so much better”

Tag: Informática Teórica,La ProfesiónJoaquim Anguas @ 10:31 am

After more than 30.000 people signed this petition , Mr. Gordon Brown, Prime Minister UK, says sorry to Mr. Alan Turing in an article for the Daily Telegraph. I have to say I was a bit reluctant regarding the petition because in a way it may mean that Mr. Turing deserved it more than others because of the contribution he made to his country during The War. But Mr. Brown answer does not forget all those who suffered the same treatment as Mr. Turing at that time.


It is impossible to summarize here the contribution that Mr. Turing did to Computer Science.

Most media is focusing lately in the Turing Test. I almost see this like a joke that many took seriously. I just hope that popular belief does not convert the Turing Test into a real metric.

But to name one outstanding contribution, to me the Turing Machine was the ultimate calculus model at the time, which allowed him and others to dig deeper on Computational Complexity Theory.

As Mr. Brown said, “You deserved so much better”, Mr. Turing.

Mar 03 2009

Georg Cantor, feliz cumpleaños

Tag: 01,Informática Teórica,La ProfesiónJoaquim Anguas @ 11:55 pm

3D Cantor Set

En un día como hoy pero en 1845, nacía en San Petersburgo, Rusia, Georg Cantor. Padre entre otros de la Teoría de Conjuntos, del Argumento de la Diagonal y del Teorema de Cantor, estos resultados resultan inspiradores o imprescindibles en el posterior desarrollo de las bases de la Teoría de la Calculabilidad (Teoremas de Incompletitud de Gödel o Problema de la Parada)

Cantor fue diagnosticado póstumamente de un trastorno bipolar y hay quien dice que estaba convencido de que Dios le había elegido para comunicar a la humanidad conceptos como los números transfinitos.

Puede resultar sorprendente, pero bien pensado si a cualquiera de nosotros se nos hubiese pasado por la cabeza una sola del conjunto de ideas brillantes que Cantor concibió, quizás también nos consideraríamos inspirados por el Altísimo.

Continue reading “Georg Cantor, feliz cumpleaños”