Tasks and Tools
You have m different tasks to complete and to help you, n different software tools you could purchase, each with a positive integer cost ci . You have no choice about which tasks to complete (you must complete them all), but you get to choose which tools you will purchase.
Tools are not necessary to complete tasks; however, certain tasks have additional costs if they are completed without the use of specific tools. Information about these additional costs is provided through non-negative integer dependencies: for all pairs i; j, di;j is the additional cost of completing task i without tool j —a dependency can be equal to zero to indicate that there is no additional cost.
Finally, there are known incompatibilities between certain tools: for each tool i, you have a list of all the other tools with which tool i is incompatible. Obviously, it is not possible to install incompatible tools at the same time.
Give a Linear Programming (or Integer Programming) solution to determine which tools to pur-chase in order to minimize your total cost (from the purchase of tools and the dependencies). Please write your algorithm in pseudo-code and include a high-level English description (either separately or as comments throughout your algorithm). Also, remember to justify the correctness of your solution—this is important!
P, NP, and coNP
For each decision problem below, state whether it belongs to P, NP, or coNP—make the strongest claim that you can. Justify your answer by giving an algorithm of the appropriate type together with a brief argument that it satisfies the required properties.
AllSmallCycles (“ASC” for short)
Input: Graph G = (V ; E), edge weights w : E ! Z+, vertex s 2 V , bound B 2 Z+.
Question: Does every cycle in G that starts at vertex s have total weight no more than B?
AllLargeCycles (“ALC” for short)
Input: Graph G = (V ; E), edge weights w : E ! Z+, vertex s 2 V , bound B 2 Z+.
Question: Does every cycle in G that starts at vertex s have total weight at least B?
Dept. of Computer Science, University of Toronto, St. George Campus page 1 of 2
CSC 373 H1 Assignment #4
SomeLargeCycles (“SLC” for short)
Input: Graph G = (V ; E), edge weights w : E ! Z+, vertex s 2 V , bound B 2 Z+.
Question: Does some cycle in G start at vertex s and have total weight at least B?
SomeSmallCycles (“SSC” for short)
Input: Graph G = (V ; E), edge weights w : E ! Z+, vertex s 2 V , bound B 2 Z+.
Question: Does some cycle in G start at vertex s and have total weight no more than B?
Properties of !p
Give a detailed argument that for all decision problems D1; D2; D3, D1 !p D2 and D2 !p D3 implies D1 !p D3.
Suppose D0 is some NP-complete problem and D is any decision problem. What can we conclude about D if we know that D0 !p D and D !p D0? Make the strongest claim you can and prove it.
If D is NP-complete and D 2 coNP, what can we conclude? Make the strongest claim you can and prove it.
Dept. of Computer Science, University of Toronto, St. George Campus page 2 of 2
