Tried to get #stablediffusion to solve the p=np problem. Can some #mathematicians help explain these results? I wanted to be fair so I asked it in both orders.
Prompt: "pure red background if p=np, but a pure blue background if p!=np"
#BingChat (precise) has concluded that P=NP
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
#ComputerScience #complexity #PequalsNP #NPhard #NPcomplete #python #GraphTheory
https://youtu.be/ctwX--JEzSA The secret link between thousands of math problems
Oh, polynomial3sat.org is down and the respective code on GitHub is removed. The corresponding paper on arXiv is still accessible. Does anyone know more about what happened?
https://arxiv.org/abs/1903.10081
#satsolving #complexitytheory #PequalsNP #compsci #theoreticalcomputerscience
In this paper, we provide a deterministic polynomial time algorithm that determines satisfiability of 3-SAT. The complexity analysis for the algorithm takes into account no efficiency and yet provides a low enough bound, that efficient versions are practical with respect to today's hardware. We accompany this paper with a serial version of the algorithm without non-trivial efficiencies (link: polynomial3sat.org).
geeknik
jordan
Bornach
Thong Kuah
Mark Crowley
Stephan Beyer