I asked it to write a Python script that when given a graph where there are no more than 5 edges for every vertex, it returns the length of the longest path that visits each vertex no more than once. Then lifted the edge count restriction.
In both cases it claimed polynomial time complexity to solve an NP-hard problem
@bornach Not that I'm going to argue I''m right about this, but I believe from that horrible Discrete Structures class that determining the shortest path in a graph is an NP-hard problem. But I hated that class with a passion.
Add comment