For this questions I need well explained answers to the very last detail of proof as soon as possible

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

• 1495511075-Algorithms.pdf

ComputerScienceExpert

(11)

Status NEW Posted 23 May 2017 03:05 AM My Price 8.00

-----------

Attachments

file 1495511077-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer