Alice and Bob go out on a date at a nice restaurant. At the end of the meal, Ali

Question

Alice and Bob go out on a date at a nice restaurant. At the end of the meal, Alice has eaten cA dollars worth of food, and has in her wallet a set of bills A = {a1 , a2 , . . . , an }. Similarly, Bob owes the restaurant cB dollars and has bills B = {b1,b2,...,bm}.

Now, Alice and Bob are very calculating people, so they agree that each of them should pay their fair share (cA and cB, respectively). One thing they don’t mind doing, however, is fairly trading bills.

That is, Alice can exchange a subset A A of her bills for for a subset B B of Bob’s bills, so long as aA a = bB b.

Under the above conditions, Alice and Bob wish to find, after trading as many times as desired, subsets of their bills A, B such that aA, a=cA and bB, b=cB. Prove that FAIR DATE is NP-complete. You may assume subset-sum is NP complete.

Explanation / Answer

assumuming that subset-sum is NP complete:

1)a=cA is Total sum that Alice could pay.

2)b=cB is Total sum that Bob could pay.

note: Alice's total sum is equal to Bob's total sumAlice which says as Alice exchange a subset A A of her bills for for a subset B B of Bob’s bills, so long as aA a = bB b. (which is result of sum of subsets).

1)Show it is in NP:

In other words, given some information C, you can create a polynomial time algorithm V that will verify for every possible input X whether X is in your domain or not.

Example

For a given set A and sum S the algorithm returns the sum of sub sets of set A which equals to S.

Now,for every set A and sum S , there exit subsets which is NP.

Note that algorithm P should work for every set A and sum S. For every input there should exist information that could help us verify whether the input is in the problem domain or not. That is, there should not be an input where the information doesn't exist.

Prove FAIR DATE is NP Hard

This involves getting a known NP-complete problem like SAT, the set of boolean expressions in the form:

(A or B or C) and (D or E or F) and ...

where the expression is satisfiable, that is there exists some setting for these booleans, which makes the expression true.

Then reduce the NP-complete problem to your problem in polynomial time.

That is, given some input X for SAT (or whatever NP-complete problem you are using), create some input Y for your problem, such that X is in SAT if and only if Y is in your problem. The function f : X -> Y must run in polynomial time.

In the example above, the input Y would be the graph G and the size of the vertex cover k.

For a full proof, you'd have to prove both:

that X is in SAT => Y in your problem

and Y in your problem => X in SAT.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.