In this repository I will publish my experiments regarding the P-NP-Problem (which is one of the Millennium Prize Problems and one of the most important unresolved problems of the theoretical computer science and computational complexity theory). Especially the Traveling Salesman Problem (TSP) as one of the NP-complete problems is in focus of my experiments in here. The algorithms are - for experimentations sake and exact comparable calculations - implemented in Python 3 and follow an example for a TSP from the University of Helsinki in its online course on "Building AI" (via Elements of AI), which inspired me besides my cooperative studies in computer science at Berlin School for Economics and Law and pracitical phases at DB Systel GmbH to use some of my free time on it - as I think this could also be a useful training for problems I will probably face while I'm working at DB Systel GmbH or in general for a railway or logistics company.
/tspiteration/01-iterate-tsp.py is my first naively implemented and logically scaleable - but not runtime scaleable - exact solution to the TSP with mainly a brute-force approach and different list operations - written in Python. The asymptotic runtime would be O(n!), which is no solution in terms of efficiency and with this far away from a solution to the overall P-NP-Problem.
/tspiteration/02-greedy-tsp.py is my second implemented algorithmic approach, also a logically scaleable and this time also runtime scaleable - but not exact - solution to the TSP with mainly a greedy approach - written in Python. The asymptotic runtime would be O(n^2), which is a polynomial solution in terms of efficiency but not an effective solution to the overall P-NP-Problem.
/tspiteration/03-compare-tsp.py is my third implemented algorithmic approach, also a logically scaleable and this time also runtime scaleable - but not exact - solution to the TSP with mainly an option comparing greedy approach - written in Python. The asymptotic runtime would be O(n^2), which is a polynomial solution in terms of efficiency but not an effective solution to the overall P-NP-Problem.
/hypothesis is a collection of my fourth implemented algorithmic approach, this time in form of a documented mathematical hypothesis at the beginning - observing differences between graphs and maps or coordinate systems - ending up in an approach to the problem, which is also known as Euclidean TSP in the world of mathematics. The vacuum algorithm was first proven graphically for certain types of graphs, then falsified for certain types of graphs - and thus ended up as an heuristic solution. Following this algorithmic approach, vibecoding was needed in my case to simulate the algorithm visually and to check whether it comes to a correct solution - the result is seen in /hypothesis/04-simulation-tsp.py - which is no solution per definition to the overall P-NP-Problem, as it is an efficient algorithm with asymptotic runtime of O(n log n), but delivers not the exact output for any given input. To run /hypothesis/04-simulation-tsp.py the Python package PyQt6 needs to be pre-installed / pip-installed as commented in the code.
/mathematics is a mathematical approach and attempted proof to show that P ≠ NP, with observing the number sets and cardinalities of those number sets of the given input of an Euclidean TSP like in the /hypothesis before. The attempted proof tries to state, that the input possibilities can be endlessly complex and with this there can not exist an algorithm with polynomial asymptotic runtime as we can always overcomplicate the input with the continuum of n. As discussed with some professors, this seems to be not an accepted proof to the overall P-NP-Problem. But I've got some gut feeling, that it's fundamentally the right idea and a trace to follow.
...maybe more to come...