A question on sub-graph isolation

[Morteza]

I am working on a problem and I was wondering if you could help me to find an answer: We consider a complete graph with +1 or -1 edges (weights). We want to determine whether there is a sub-graph for which sum of the weights (edges) with the remaining sub-graph is less than 0. I want to know whether there is any polynomial algorithm for this problem.
We divide the nodes of the graph into two sub-graphs and consider only the edges between these two parts, edges with one end in the first part and the other end in the second part (the edges are undirected). If we divide graph G into two parts G1 and G2 then we will have |G1|*|G2| edges between them (the graph is complete). We consider the sum of these edges as the weight between the sub-graphs (parts).  Can we determine polynomially if there is a partitioning for which the weight is negative? i.e. there are more negative edges than positive edges between two parts.
Best Wishes,
Morteza

[Algolist.net Editor]

The naive algorithm is obvious: look over all subsets of a vertex set and give an answer. But it is O(2ⁿ). I thought of greedy approach to apply here, but can't prove, that it gives a correct result yet.