Re: compression algorithm is NP complete problem?

In article <d473dh$9l8$1@xxxxxxxxxxxxxxxxxxxxxxx>,
Mauricio Nivaldo Andres Monsalve Moreno <mnmonsal@xxxxxxxxxxxxx> wrote:

>Indeed if you think about minimal space. That minimal usage problem is
>known as knapsack. But if you think about the algorithm itself, and
>the problem of logical decompressing, I don't know.
>
>A practical aproach to NP complete problems might be thinking of a PC as
>a deterministic machine (most certainly). So a BIG problem, such
>optimization problems, may take exponential time solving the problem
>(finding the optimal solution). An example is the salesman problem. If
>you think about 10 cities, you can solve it in no time. Think about 100
>cities, you'll die before the program stops (and your children will die,
>too).
>
>A practical aproach is knowing. I've faced some NP hard optimization
>problems around there. E.g. a factory asks you to solve a problem that
>requires optimization. If you identify the problem, and you say that the
>problem is NP hard, then you can convert it into a NP c??mplete problem,

Actually, not every NP-hard problem is NP-complete: some NP-hard problems
are harder than every NP problem (including the NP-complete ones).

>then find a heuristic and solve the problem. And you know that every NP
>problem can be reduced to a NP complete problem. And if you look for
>fast and efficient heuristics for those problems, you can solve your
>problem in polynomial time, but with less accuracy.
>
>I hope this is practical enough...
>...and sorry for my bad english
>

--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------
.