Reference no: EM131182312
You may consult with others concerning the general approach for solving problems on assignments, but you must write up all solutions entirely on your own. Copying assignments is a serious academic offense and will be dealt with accordingly.
1. The decision problem PARTITION is defined on page 13 of the Notes NP and NPCompleteness". (You may assume that a1; : : : am are positive integers.)
Define the associated search problem PARTITION-SEARCH and give an algorithm showing that
PARTITION-SEARCH ! p PARTITION.
Give a loop invariant for your algorithm.
2. Consider the problem DISTANCE-PATH.
DISTANCE-PATH
Instance
hG; s; t; di, where G is an undirected graph, s and t are nodes in G, and d is a positive integer.
Question Is the distance from s to t exactly d? In other words, is it the case that there is a path of length d from s to t, and no shorter path from s to t?
(a) Show that DISTANCE-PATH 2 NL.
(b) Show that DISTANCE-PATH is NL-complete.
Hint: Show that P AT H =L DISTANCE-PATH. Given a directed graph G construct an undirected graph G0 by making n copies of G. Each edge in G0 goes from copy i to copy i + 1.
3. Use a padding argument to show that NL = coNL implies NSPACE(n3) = coNSPACE(n3). See Problem 9.13, in the textbook for a description of padding.
4. Show that T QBF = 2 DSPACE(n1=5). You may refer to the proof of Theorem 8.9 in the text, and assume the fact that the reduction presented there can be carried out in log space.
|
Difference between velocity and acceleration
: In 250 words give an example (not out of the book or from the Internet) which illustrates the difference between velocity and acceleration.
|
|
Will you use subcontractor for different part of the project
: Will you use subcontractors for different parts of the project? How will you maintain contact communication? How will you track progress, milestones, and setbacks? How will you monitor resources and budget?
|
|
Describe the risks and benefits with leading
: First, describe the risks and benefits with leading, meeting, and lagging the market in overall compensation and benefits. Next, choose the appropriate strategy (lead, meet, or lag) for Dan-Mat Corporation, and provide rationale about why this is app..
|
|
Construct strategy for managing higher ranged product brands
: Determine any strategic partnerships the department store chain could develop that would help promote the higher-ranged-priced products and support the expansion in the west coast.
|
|
Define the associated search problem partition
: Define the associated search problem PARTITION-SEARCH and give an algorithm - Show that DISTANCE-PATH 2 NL.
|
|
Inform the contractor of privately
: What methods will NJDEP use to inform the contractor of privately held submerged land parcels that cannot be entered?
|
|
Argon and the surrounding atmospheric air
: No heat transfer takes place between the argon and the surrounding atmospheric air, which is at T0 300 K and P0 100 kPa. Determine (a) the useful work output, (b) the exergy destroyed, and (c) the reversible work for this process.
|
|
Exergy of the combined system
: Assuming the water that vaporizesduring the process condenses back in the tank and the surroundings are at 20°C and 100 kPa, determine (a) the final equilibrium temperature, (b) the exergy of the combined system at the initial and the final states..
|
|
Pillars of the marketing code of ethics
: Evaluate the company's past performance marketing their product using the six pillars of the marketing code of ethics (as set forth by the American Marketing Association) --honesty, responsibility, caring, respect, fairness, and citizenship
|