Here the earlier version one, without division for record. I update the original for the new version.

# -*- coding: cp1252 -*-
from itertools import chain

class Term(object):
    __slots__ = 'coeficient', 'exponent'
    def __init__(self, coeficient=1.0, exponent=0):
        self.coeficient = coeficient

        if isinstance(exponent, int):
            self.exponent = exponent
        else:
            raise ValueError('Exponent must be integer!')

    def __nonzero__(self):
        return self.coeficient

    def __iter__(self):
        yield self

    def __len__(self):
        return 1

    def __neg__(self):
        return Term(-self.coeficient, self.exponent)

    def __abs__(self):
        return -self if self.coeficient < 0 else self

    def __add__(self, other):
        if hasattr(other, 'exponent') and self.exponent == other.exponent:
            return Term(self.coeficient + other.coeficient, self.exponent )
        else:
            return Polynomial(self) + Polynomial(other)

    def __sub__(self, other):
        if hasattr(other, 'exponent') and self.exponent == other.exponent:
            r = (Term(self.coeficient - other.coeficient, self.exponent) if self.coeficient != other.coeficient else Term(0))
        else:
            r = Polynomial(self) - Polynomial(other)
            r.simplify()

        return r

    def __mul__(self, other):
        if hasattr(other, 'exponent'):
            r = Term(self.coeficient * other.coeficient, self.exponent + other.exponent)
        else:
            print self, other, type(other)
            r = Polynomial(self) * Polynomial(other)
            r.simplify()
        return r


    def __div__(self, other):
        return Term(self.coeficient / other.coeficient, self.exponent - other.exponent)

    def __cmp__(self, other):
        if not isinstance(other, Term):
            other = Term(other)

        if self.exponent == other.exponent:
            if self.coeficient < other.coeficient:
                return -1
            elif self.coeficient > other.coeficient:
                return 1
            else:
                return 0

        elif self.exponent < other.exponent:
            return -1
        elif self.exponent > other.exponent:
            return 1
        else:
            return 0

    def __str__(self):
        """ 1 as coeficient shown only for exponent 0 (constant), exponent 1 not shown """
        return ((str(self.coeficient) if self.coeficient != 1 or self.exponent == 0 else '') +
                ((("X^%i" % self.exponent) if self.exponent and self.coeficient else '')
                 if self.exponent != 1  else 'x'))

    def __repr__(self):
        """Show all zero coefficient Terms as Terms() except True zero"""
        return 'Term(%s, %i)' % (self.coeficient, self.exponent) if self.coeficient or self.exponent==0 else 'Term()'


class Polynomial(list):

    def __init__(self, *args):
        if len(args) == 1:
            if args and isinstance(args[0], Polynomial):
                args=args[0]
            elif not isinstance(args[0], Term):
                args=Polynomial(Term(args[0]))

        self[:] = args 
        self.simplify()

    def __str__(self):
        #shows the Term list on screen
        r = '('
        for v in self:
             # separate sign for use as minus between Terms except for first term
             r +=  ('%s%s' % ( (' - ' if r != '(' else '-') if v.coeficient < 0
                               else (' + ' if r != '(' else ''),
                               # do not show + 0 for Terms with Zero coeficient
                               abs(v)) if v.coeficient else ''  
                   )
        return r + ')'

    def __repr__(self):
        return 'Polynomial(%s)' % ', '.join(repr(v) for v in self)

    def simplify(self):
        assert all(isinstance(item, Term) for item in self), 'Not all items are Terms: %s' % list(self)
        if len(self)<=1:
            return
        self.sort(reverse=True)
        i = 0
        while i <= len(self) - 1:
            if i < len(self) - 1 and self[i].exponent == self[i+1].exponent:
                self[i] =  self[i] + self[i+1]
                del self[i+1]
            elif not self[i].coeficient:
                del self[i] 
            else:
                i += 1
        return self

    def __neg__(self):
        return Polynomial(*(-v for v in self))

    def __add__(self, other):
        r = Polynomial(*chain(self, other))
        r.simplify()
        return r

    def __sub__(self,other):
        return self + -other

    def __pow__(self, n):
        if n != int(n) or n < 0:
            raise ValueError('Invalid power exponent: %s' % n)
        elif n == 0:
            return Term(1)
        else:
            r = self
            for c in range(n-1):
                r *= self
            return r

    def __mul__(self, other):
        p = sum((a * b for a in self for b in other), Term(0))
        p.simplify()
        return p

m = Term(5,2)
print m + Term(4,2) + Term(4) + Polynomial(Term(23, 2), Term(2,0), Term(-5, 3))
x1 = Polynomial(Term(1,1), Term(-1))

print '%s * %s = %s' % (x1,x1, x1 * x1)
print '%s ** %i = %s' % (x1, 2, x1 ** 2)

Very interesting. Can you post it somewhere too, so that I can copy-paste it and try it?
As a gist, for example:
https://gist.github.com

You just double click the post and copy/paste, no need to put it external site, where it could be removed and the link broken.

Seeing your previous posts on http://pypol.altervista.org/index.html I am avaiting your response with interest. Maybe you can point some loopholes in my code to improve my chances in the code snippet competition

Of course, my C++-brain cringes at the sight of all the blantant inefficiencies in the code, but if I adopt the Python mindset, then your code snippet is quite nice! Lots of demonstrations of Python-kung-fu in there.

A few comments:

I think you are not protective enough of your invariants, and you suffer from constantly breaking and repairing them. By invariants, I mean the fact that a Polynomial is always a list of terms, in a sorted order, with unique exponents only. Basically, what the "simplify" function enforces. Many of your operations on the Polynomial, like addition, substraction, multiplication, power, etc. can all be performed entirely without breaking the invariants. For example, your addition function chains the two lists of terms, which creates a "polynomial" list whose invariants are broken, and then you repair it with "simplify". You are not taking advantage of the fact that your two input Polynomials contain sorted unique-exponent terms. You could "merge" the two Polynomials very easily, resulting in another Polynomial with valid invariants, without having the "simplify" it afterwards. The whole point of having invariants in a class and protecting them through encapsulation is to be able to avoid having to constantly check or repair the invariants, and to be able to simplify operations by relying on the invariants being respected on the operands. Consider that in the future.

It would have been a lot nicer if your test program was written in easier terms by using the DSEL that you just created (DSEL: Domain-Specific Embedded Language). I see no reason why you couldn't simply construct polynomials like this:

x = Polynomial(Term(1,1))

p1 = 2 * x**2 + 4 * x + 6
p2 = 6 * x**6 + 3 * x**5 + 10 * x**3 + 23 * x**2
p3 = (x + 1) * (x**2 + 3*x + 1)

Or is there a reason why the above wouldn't be possible? If not, I think this is a much nicer way to use this Polynomial class, it is much nicer syntax than those horrible-looking expressions like Polynomial(Term(1,3), Term(-12,2), Term(-42)) instead of simply x**3 - 12 * x**2 - 42. Of course, the latter is very inefficient compared to the first, but that's not a result of the syntax, it's a result of the first problem I mentioned, which is easy to fix.

I think it would also be a nice addition to be able to parse string expressions of the same format as the to-string conversion.

I should look into it if it is possible to do quick operation to do merging and combining the same time the equal powers. But simplification also takes care of droping the 0 multiplier terms and it uses the C-speed sorting (minus the penalty of comparision operations defined in user class) which I would expect to not cause much penalty with typically less than 100 term polynomials case. Maybe there could be internal _simplify method wich expects the powers to be in order, only combining same order terms and dropping null terms. It could be much non-DRY code compared with simplify method and slow down by extra comparisions needed. Probably I would end up to use that inside the simplify by only moving after sorting part to this new function. That would of course hit performance of all operations by one more function call.

The idea of using not performance critical place the normal expression with x = Polynomial(Term(1,1)) but using x = Term(1,1) should be more efficient as power of Monomial is very simple compared to the binary recursive implementation of Polynomial power. That would also make it simple to do safe evaluation (see my other code snippet MathExpression) with the x variable defined only in the eval. I would do that as fallback if arguments are not of Polynomial or Term type by try...except.

I probably have also unnecessary simplify in add operation, I must recheck it (as Polynomial creation allready does simplification as terms for creation of Polynomial) I will recheck it when I get to my own computer.

This code should also be run with -O option to avoid executing the assert statements to or asserts should be commented out, if used in real world usage.

Also I do not find the expressions of polynomials to be so hard to read with regular representation expressions. But maybe it is just the old Lispers opinion.

I will try to do some reasonable profiling with non-simplifying __add__ and post the results of the timing.

I should look into it if it is possible to do quick operation to do merging and combining the same time the equal powers. But simplification also takes care of droping the 0 multiplier terms and it uses the C-speed sorting (minus the penalty of comparision operations defined in user class) which I would expect to not cause much penalty with typically less than 100 term polynomials case.

It is the same operation as you do when doing merge-sort, plus the "remove zeros" and "fuse equal exponent terms" parts which can be trivially inserted into the merge operation. My Python skills are too shameful to demonstrate it, but if something is trivial (<10 lines) in C/C++, I would presume it is even simpler in Python.

Currently, your "simplify" function has the following complexity. Assume the polynomial has N terms, the sorting takes O(NlogN) while your pruning+fusion of terms takes O(N^2) (because of the inefficient use of random-accesses in a sequential container), but of course, of implemented correctly, the pruning-fusion would have O(N) complexity. So, if A is the cost of comparing/swapping elements, and B is the cost of checking the pruning condition, then you time consumption is A * N * logN + B * N + O(1). If you use a merge-while-pruning approach, the overall time consumption will be (A + B) * N + O(1). If N is 100, you would roughly get 700 * A + 100 * B for the "simplify" approach, and about 100* (A + B) for the merge-while-pruning approach, leading to a benefit of about 600 * A, in other words, the "simplify" approach is likely to be several times slower in such a case, regardless of how fast your "C-speed" sorting is. And, this analysis also disregards the additional overhead coming from the sort method (in addition to the compare-swap cost A), and, the fact that at such small N values, most standard implementations revert back to an insertion-sort algorithm (at least, GCC does) with O(N^2) complexity but less overhead.

The point is, when you are merging two sorted arrays, you should use an algorithm for merging two sorted arrays. In fact, one of the classic coding mistakes that you see all the time is people abusing sorting algorithms by using them for everything. Sorting algorithms are much less useful than people think, because you rarely have a situation where you start with a completely scrambled array and want to sort it entirely. Usually, you want to keep track of the min/max elements (use a "heap" for that), or you only need to merge or insert elements into an already sorted list (use a "merge" for that, or keep a BST), or you only need specific partitions of the list (use a quick-select algorithm for that), or you want the first K minimum/maximum elements of a list (again, with quick-select), etc... Sorting is only for when you start with a complete and unordered list, and want an ordered list at the end, just about every other case can be handled more efficiently otherwise, and yes, it does make a difference, empirically and theoretically.

It could be much non-DRY code compared with simplify method

I guess "DRY = Don't Repeat Yourself". That's the core of the issue. Don't repeat yourself doesn't necessarily mean reuse as much as possible. The "simplify" function does a lot more than what the "add" function needs, hence the performance penalty. The DRY rule might be analogous to saying that if you have a car that you use to do your grocery shopping, you can also use it go to the mall, i.e., that you don't need to buy another car for that other purpose. However, DRY doesn't mean that if you happen to own a tank, that you should take it to the mall. You can, but it's overkill and wasteful (and it will scare people sh1tless!). DRY means that you should use the same function for "add" and "sub" because the need is essentially the same. So, to me, the "simplify" method is non-DRY code already, and a merge-while-pruning approach would fix that.

Probably I would end up to use that inside the simplify by only moving after sorting part to this new function. That would of course hit performance of all operations by one more function call.

One hint on improving your implementation: You could easily do without the "simplify" function altogether. You are already calling it in places you don't need to call it, and most of the operations can be done without it or with a merge-while-pruning or similar strategy. You can ponder on that for a while.

I produced version using the heapq.merge instead of mixing the sorting order. I have not tested performance compared to earlier version, but probably bigger improvement have come of removing the epsilon equality test for Term. I also used simplification only from the Polynomial initialization and moved out the sorting part from the simplify function.

I guess "DRY = Don't Repeat Yourself". That's the core of the issue.

Should we call non-DRY WET = Write Everything Twice ;)

I used the negation trick for substraction for Polynomial (later also Term, but I think I coded it to repeat the logic for showing doing it both ways) and not using references to coeficient and exponent but using Term addition to do slower way in the simplify, as I feel it very ugly to reimplement the Term addition in Polynomial class, even we loose benefit of knowledge that the Terms are of same order for sure and only coefficients need to be added.

Practically the code is repeated like in implementation of fractions module.

    def _add(a, b):
        """a + b"""
        return Fraction(a.numerator * b.denominator +
                        b.numerator * a.denominator,
                        a.denominator * b.denominator)

    __add__, __radd__ = _operator_fallbacks(_add, operator.add)

    def _sub(a, b):
        """a - b"""
        return Fraction(a.numerator * b.denominator -
                        b.numerator * a.denominator,
                        a.denominator * b.denominator)

    __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)