# complexity theory – How to know if the problem belongs to conp?

Hello everyone I am new to the site, a few days ago I had a test and could not pass it.

There is a question that I did not answer correctly and did not understand:

There will be an list of items. Suppose we have two players (the first and second).

There will be the value function of item meaning:

• The value of the item is not negative (at least – zero).
• Values are not necessarily integers.

Also the value of item group is defined as .

Let’s look at the MMS problem in two players. Our goal is to divide all the items between the two players (that is, to divide them into two foreign groups whose unity is all the items).

We will count all the possible divisions 1,2,3 … and so on. Given the i division, , of all possible divisions, we denote by the value of the smaller subgroup of . This means: . We will set a minimum-maximum value (Maximal Minimum Size) as .

For example: there are 4 items . Their value: .
The possible divisions are:

• , {2,3,4,5} – The value of the small subgroup is 0.
• {2} , {3,4,5} – The value of the small subgroup is 2.
• {3} , {2,4,5} – The value of the small subgroup is 3.
• {4} , {2,3,5} – The value of the small subgroup is 4.
• {5} , {2,3,4} – The value of the small subgroup is 5.
• {2,3} , {4,5} – The value of the small subgroup is 5.
• {2,4} , {3,5} – The value of the small subgroup is 6.
• {2,5} , {3,4} – The value of the small subgroup is 7.

It is not important to arrange between the subgroups, so these are all possible divisions. The maximum minimum value is 7, and is obtained from the division {2,5} , {3,4}.

In the decision version MMS(E, v, z), given items , value function and non-negative number z, we are asked – Is the maximum minimum value equal to z?

question 1 :
Determine to which equivalence department the language belongs:

1. 2. 3. 4. It is not known whether or not

question 2 : Who will be the witness or algorithm that will see this?

1. There is a polynomial algorithm divides the items in a greedy among all players
2. A non-belonging verification algorithm can be constructed. Our witness will be some division into two sub-groups. The validation algorithm will check whether . If so, a sign that the -z given to us is not the minimum-maximum value, since there is a division where the minimum value is greater than -z.
3. Suppose our witness is some division into two subgroups. In case z is smaller than the maximum minimum value, we can find out. But in the case where z is greater than the maximum minimum value, the witness which is a division , will not help us. That is to say, in this witness we can refute affiliation only for some of the inputs, and not for all, as required.

I do not understand these 2 questions. I could not answer them on the test.

Posted on Categories Articles