Travelling salesman problem as a PoW algorithm?

[voileipa]

Hi

I'm just wondering if the Travelling salesman problem could be used as a PoW algorithm?

[spartacusrex]

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)

[tromp]

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...

[voileipa]

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.

[dannon]

Eh. I'm not sure why you would want that. Is there a benefit for using that algo?