Show Bid Request Hamiltonian Path Problem Bid Request Id: 54023 Bookmark in my 'To Do' list Posted by: ishan_i (4 ratings) (Software buyer rating 9.75) Non-action Ratio: Above Average - 25.00% Buyer Security Verifications: Good Approved on: Mar 21, 2003 2:28:15 PM EDT Bidding Closes: Mar 22, 2003 6:13:08 PM EDT Viewed (by coders): 67 times Deadline: 3/24/2003 TIME EXPIRED Phase: 100% of work completed and accepted. Coder has been paid. Max Accepted Bid: Bidding is closed Project Type: Personal Project / Homework Help Bidding Type: Open Auction Categories: Documentation / Tech Writing Enter chat room for this bid request (0 active users at Jul 15, 2003 11:10:46 PM EDT) Description: 1. Write down a non-deterministic algorithm that solves the Hamiltonian Path Problem (HPP), and runs in polynomial-time. Deduce that HPP is NP. 2. Define a polynomial time-reduction of HPP to HCP (Hamiltonian Circuit Problem). 3. Define a polynomail time-reduction of HCP to HPP. 4. Assuming that HCP is NP-complete, prove that HPP is also NP-complete. Deliverables: 1) Written answers to the above assignment. 2) Complete ownership and distribution copyrights to all work purchased. Platform: None, as it is a written assignment. Must be 100% finished and received by buyer on: Mar 24, 2003 EDT Deadline legal notes: All times are expressed in the time zone of the site EDT (UT - 5). If the buyer omitted a time, then the deadline is 11:59:59 PM EDT on the indicated date. Remember that contacting the other party outside of the site (by email, phone, etc.) on all business projects < $500 (before the buyer's money is escrowed) is a violation of both the software buyer and seller agreements. We monitor all site activity for such violations and can instantly expel transgressers on the spot, so we thank you in advance for your cooperation. If you notice a violation please help out the site and report it. Thanks for your help.   Bidding/Comments: All monetary amounts on the site are in United States dollars. Rent a Coder is a closed auction, so coders can only see their own bids and comments. Buyers can view every posting made on their bid requests. See all rejected bids (and all comments) Name   Bid Amount    Date   Coder Rating   This bid was accepted by the buyer! DanD (40 ratings) in Bucuresti, Bucharest Romania Bid id: 582,356   $35 (USD) Mar 22, 2003 5:02:24 PM EDT  9.35 (Superb)     Ok, can you please send me the info regarding the second job ? I wouldnt wont to say that i will do it since i dont know what is about. In the meantime there are two requirements left for this job. They seem to be a little bit more complicated. Anyway.. regarding payment... i wouldnt be very happy about 30 for this job (supposing that i wont do the second). In order to get a middle choice is 35 ok ? If the second job will be as easy as you say i will be happy to do it for 15.           See 3 private reply(ies) to/from DanD.