Need detailed proof for the second, third, and fourth questions. This is about college advanced level computer science theory knowledge. All about space complexity theory. Really need help because I have no time doing this assignment.

 

CSC463SProblem Set 4Winter, 2016Due: Friday, April 1, beginning of tutorialNOTE: Each problem set counts 15% of your mark, and it is important to do your ownwork. You may consult with others concerning the general approach for solving problems onassignments, but you must write up all solutions entirely on your own. Copying assignmentsis 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 NP-Completeness”. (You may assume thata1,...amare positive integers.)Define the associated search problem PARTITION-SEARCH and give an algorithmshowing thatPARTITION-SEARCHp→PARTITION.Give a loop invariant for your algorithm.(See Definition 6 in the Notes “Search and Optimization Problems” for the definitionofp→.)2. Consider the problem DISTANCE-PATH.DISTANCE-PATHInstancehG,s,t,di, whereGis an undirected graph,sandtare nodes inG, anddis a positiveinteger.QuestionIs the distance fromstotexactlyd? In other words, is it the case that thereis a path of lengthdfromstot, and no shorter path fromstot?(a) Show that DISTANCE-PATH∈NL.(b) Show that DISTANCE-PATH isNL-complete.Hint:Show thatPATH≤LDISTANCE-PATH. Given a directed graphGconstructan undirected graphG0by makingncopies ofG. Each edge inG0goes from copyitocopyi+ 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 thatTQBF /∈DSPACE(n1/5). You may refer to the proof of Theorem 8.9 inthe text, and assume the fact that the reduction presented there can be carried out inlog space.1

Attachments:

• 1496713210-4.pdf