Subj : Re: stacking algorithm
To   : comp.programming
From : Omri Barel
Date : Sun Aug 07 2005 06:51 pm

<googmeister@gmail.com> wrote in message 
news:1123412945.369949.255070@g14g2000cwa.googlegroups.com...
>
> Omri Barel wrote:
>> And now we've reduced the problem to finding a minimum clique partition
>> of the graph, which is an NP problem:
>
> Of course, reducing a problem to an NP-complete problem does not
> imply the original problem is hard. If you want to establish
> intractability,
> the reduction needs to go in the other direction.
>

You're absolutely right, and in this case it's not possible - that would 
mean finding for every graph of n vertices a stack of n lines. That's not 
possible (I could give an example).

I stand corrected - I wasn't even thinking of that when I posted (and the 
way I posted implied that the original problem was NP-complete), but it's 
true; you could "reduce" the problem of sorting an array into an NP problem 
(in fact, it IS an NP problem - it takes polynomial time to check a 
solution), but it most definitely isn't NP-complete.

.