''*NP problems are tractable in the space of cellular automata in the hyperbolic plane
In this paper, we define cellular automata on a grid of the hyperbolic plane that is based on the tessellation obtained from the regular pentagon with right angles. Owing to the properties of that grid, we show that 3-SAT can be solved in polynomial time in that peculiar setting; then we extend that result for any NP problem. On this ground, several directions are indicated.*'' [source from 2001]

BTW, 3-sat does not refer to the German television channel ;)

It is this 3-sat:

*3-satisfiability is a special case of k-satisfiability (k-SAT) or simply satisfiability (SAT), when each clause contains exactly k = 3 literals. It was one of Karp's 21 NP-complete problems.*

In complexity theory, the satisfiability problem (SAT) is a decision problem [...]

The question is: given the expression, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true?

In complexity theory, the satisfiability problem (SAT) is a decision problem [...]

The question is: given the expression, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true?

Now SAT is difficult, because if you don't how to optimize your search, you basically need to go thru all possibilities, which means for a formula with n variable, you have to explore 2

^{n}cases! Therefore: exponential time complexity (in the sequential, deterministic case). And some great guys (Cook and Levin) proved that if there is a trick to evaluate SAT faster, with the same trick you can solve ALL NP problems faster, in polynomial time!

And so far nobody has found any trick that does the job (in the general case). Too bad :(

Another very nice paper on this subject is "In Some Curved Spaces, One Can Solve NP-Hard Problems in Polynomial Time" [article].

## No comments:

## Post a Comment