  It is well known that an element of the algebra of noncommutative
*-polynomials is positive in all *-representations if and only if it is a sum
of squares. This provides an effective way to determine if a given *-polynomial
is positive, by searching through sums of squares decompositions. We show that
no such procedure exists for the tensor product of two noncommutative
*-polynomial algebras: determining whether a *-polynomial of such an algebra is
positive is coRE-hard. We also show that it is coRE-hard to determine whether a
noncommutative *-polynomial is trace-positive. Our results hold if
noncommutative *-polynomial algebras are replaced by other sufficiently free
algebras such as group algebras of free groups or free products of cyclic
groups.
