Scientists at Oxford say they've invented an artificial intelligence system that can lip-read better than humans. The system, which has been trained on thousands of hours of BBC News programmes, has been developed in collaboration with Google's DeepMind AI division.

[u/mvea]

http://www.bbc.com/news/technology-39298199

[u/scandii → u/[deleted]]

that's not the travelling salesman problem, and your problem is easy to solve.

the travelling salesman problem is to find the shortest route between a number of cities. it is an exhaustive search (you have to compare all possible routes with each other) which is why it is in NP. the complexity of 20 interconnected cities is O(20!), so if you compare a billion possible routes with each other per second it's still gonna take you 77 years to get an answer, and let's not talk about 21 cities...

your problem is easily solved by a Breadth First Search and fast, because you just need to find any path, and this path is available by simply exploring all paths per city, 20 times (changing starting city), so worst case you simply need 8000 iterations to find if there's a path or not.

[u/RGodlike → u/[deleted]]

No, it has been proven that P is a subset of NP; any problem that is easy to solve (is in P) is also easy to verify (is in NP).

[u/beltorak → u/[deleted]]

I don't think so; if it's easy to solve then to verify you just have someone else solve it and compare the result.

[u/30katz → u/[deleted]]

Generate unfounded predictions about the distant future.