Show polynomial-time algorithm for gdp
Course:- Theory of Computation
Reference No.:- EM1388584

Assignment Help
Expertsmind Rated 4.9 / 5 based on 47215 reviews.
Review Site
Assignment Help >> Theory of Computation

Let the following "gold-digger problem" (GDP). You are given the map of territory consisting of set of towns connected by trails. Each trail (u, v) connecting towns u and v is labeled with dollar value w(u, v), which is value of gold you will find along that trail. You can traverse trail as frequently as you want, but you only get value of trail the first time you traverse it; subsequent traversals have no value. Each town v has lodging cost c(v), which you pay each time you enter the town.

Expedition is cyclic path which starts and ends at given town. Expedition has profit k if total value of gold found, minus cost of all the town visits, is k. Goal is to find expedition of maximum profit. Either show that there exists polynomial-time algorithm for GDP, or show that corresponding decision problem is NP-complete. If you want to illustrate that problem is hard, you may decrease from any of: SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER, SUBSET-SUM, PARTITION, HAM-CYCLE, TSP.

Put your comment

Ask Question & Get Answers from Experts
Browse some more (Theory of Computation) Materials
Explain informally, the working of the machine M. Give the language L(M ) in set notation. Provide a grammar having 12 or less rules that accepts the same language as M. What
A particular design of the two-stage CMOS operational amplifier of Fig. utilizes ±1-V power supplies. All transistors are operated at overdrive voltages of 0.2-V magnitude. T
Assume for each part of this problem that the EAX register contains 00 00 00 4F and the doubleword referenced by value contains FF FF FF 38. Determine whether each of the co
Perform the ACL test and prepare a report with your conclusions. Document your report with ACL printouts showing details of test results and the command log - Identify an op
BIT203 Professional Practice and Ethics - During week 6 you will be required to give a brief 5-8 minute presentation to the class explaining either the analysis and conclusio
If the speed of the gas relative to the rocket is 40m/s, and the mass of rocket is 4 kg, what is the initial acceleration of the rocket and what is the focal length of the le
Calculate some number x= Sum - 2K. Create new set A by add x to the set B {b1, b2,....., bn} U {x}, where the summation now is B+x. it is possible to split the numbers in A in
Construct a truth table for each of the following arguments. Determine whether each argument is valid or invalid. Justify your answer with a complete or partial truth table.