|
Title: Travelling salesman problem as a PoW algorithm? Post by: voileipa on April 05, 2017, 12:20:22 PM Hi
I'm just wondering if the Travelling salesman problem could be used as a PoW algorithm? Title: Re: Travelling salesman problem as a PoW algorithm? Post by: spartacusrex on April 05, 2017, 01:24:32 PM Doing something 'useful' with POW has long been a desire..!
A POW algorithm needs to be HARD to compute an answer, but FAST to check. How would you check whether the answer, to the Travelling Salesman problem, is the correct one ?.. (without redoing all the work to show that PATH is actually the shortest) Title: Re: Travelling salesman problem as a PoW algorithm? Post by: tromp on April 05, 2017, 02:21:54 PM I'm just wondering if the Travelling salesman problem could be used as a PoW algorithm? Sort of. If the salesman has to visit a small fixed number (e.g. 42) of cities in a huge random bipartite graph, then Cuckoo Cycle https://github.com/tromp/cuckoo fits the bill... Title: Re: Travelling salesman problem as a PoW algorithm? Post by: voileipa on April 11, 2017, 10:28:33 AM Thank you for letting me know about the Cuckoo Cycle algorithm. I remember hearing it once, but never did a deeper digging on how it works. Will definitely now.
After some research I have concluded that the original TSP does not fit as PoW since verifying the solutions requires NP time. However, in a modified version of TSP where we try to find a route < GIVEN_LENGTH the solution verification can be done in P time. Title: Re: Travelling salesman problem as a PoW algorithm? Post by: dannon on April 11, 2017, 10:30:30 AM Eh. I'm not sure why you would want that. Is there a benefit for using that algo?
|