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.

Dic 06 2010


Go to an esoteric book shop and you’ll find that every book on the shelf (on the Holy Grail, the “mystery” of Rennes-le-Château [a hoax theory concocted to draw tourists to a French town], on the Templars or the Rosicrucians) is a point-by-point rehash of what is already written in older books. And it’s not just because occult authors are averse to doing original research (or don’t know where to look for news about the non-existent), but because those given to the occult only believe what they already know and what corroborates what they’ve already heard.

Umberto Eco

Jul 19 2010

UNIJES 2010: La prueba en informática: evolución, estado actual y propuesta de formalización

Tag: Computing, Signs and Reasoning,Informática LegalJoaquim Anguas @ 6:50 pm

Esta mañana he presentado esta ponencia en el congreso UNIJES 2010: La prueba judicial.

He añadido una sección con algunas de mis presentaciones y publicaciones aquí.

Mar 18 2010

Semantic Levels and Computer Evidence

Semantic Levels

As I had explained here, I consider there is a meaning construction, from magnetic fields in the surface of a disk to high level facts we can map to real world, when we talk about computer evidence. This contruction occurs in steps and every step involves a semiosis, up to high level facts.

It is in this last level in which a judge can render them into the final award applying all the arguments presented by the parties and regulations that rule the process.

There’s a state of opinion that defends that computer evidence that has been blessed by digital signature can slip into the process without the intervention of an expert witness: it can be treated as a document.

Don’t get me wrong, I am not saying that computer documents do not deserve this. But I am not talking about word processor or PDF files here, documents that have a meaning by themselves into the procedure. We are talking about something like a log file. And in general, I consider a log file a computer evidence, not a document.

In my oppinion this may lead to the following problem:

Continue reading «Semantic Levels and Computer Evidence»

Abr 07 2009

Abstraction layers in computational semiotics

Tag: Computing, Signs and ReasoningJoaquim Anguas @ 6:11 pm

Computational semiotics is often related to semiosis or semantics, but less to pragamatics.

Within the area of study I am interested in, it is relevant how computational signs construct a meaning you can derive high level facts from. So semiosis, semantics, but pragmatics as well, are involved.

In computation, facts are observed by accessing data stored in computational means. Data is stored in different ways, but it generally materializes in the form of bits as the minimum sign unit.

Common storage media are hard disk drives, optical media or RAM-like. Those media store bits in different ways: a magnetic field on the coating of a disk, “holes” on the optical layer of a resin disk or electrons into memory cells.

The equivalent of finding a cigarette butt in a crime scene would be to observe these signs directly. But we don’t use to get facts from this kind of signs.

Continue reading «Abstraction layers in computational semiotics»

Abr 06 2009

Expert witness, computing and presumptions

Tag: Computing, Signs and ReasoningJoaquim Anguas @ 4:56 pm

I start a series of posts related to legal reasoning and computational semiotics.

This post informally analyzes and puts into context the argumentation and generalization elements used by expert witness in computing, taking into account their relationship with computational semiotics.

If semiotics is the science of signs, computational semiotics is the branch of semiotics that studies signs supported by computational means.

Expert witness in computing, derive assertions from computational signs and argumentation methods.

While it could be thought that expert witness provide feasible assertions, the fact is that, in the field of computing, often many plausible options coexist. Expert witness use informal logic approaches like non-monotonic abductive reasoning to identify the best explanation that satisfies coherence with all other known facts.

Continue reading «Expert witness, computing and presumptions»