The necessity of forming coalitions in multi-agent system (MAS) arises in situations, when there is no agent, which can fulfil given task. In this situation we need to form group of agents to fulfil given task. This group is called coalition of agents. It may also be useful to assign group of agents to the task when the group's performance is more efficient than the performance of the single agent. The usual situation is following: We have given set of tasks for given multi-agent system. Our goal is to find the set of groups (coalitions) of agents, that fulfils all tasks so that the performance of MAS is maximal possible. Previously mentioned set of groups is called coalition structure. Of course the question how to define performance of the system arises there. The performance can be defined in many ways and in next sections we will show how this definition can impact complexity of the solution of given problem.