What is ChatGPT?
The team at OpenAI has recently released a new and improved general purpose chatbot, which is capable of interacting with the user in a conversational way. As of the date this article was published, ChatGPT is still under research preview, therefore it's free to use.
To start a conversation with ChatGPT, simply navigate to chat.openai.com and, after signing in with your account, you will be able to ask your question by typing it in an input field. It works very similar to other chatbots, which you might have already used on the web (such as Insomnobot).
First impressions and controversy
Conversations with ChatGPT have taken the internet by storm. Some of them are purely philosophical, others are political, while most are simply about programming and solving problems.
In fact, a few users took the opportunity to make use of this free trial to bump their Stack Overflow reputation by answering questions they know little about. As a result, the moderators of the site are temporarily banning submissions that are suspected to originate from ChatGPT (source). The discussions that sparked from such policy left the community divided. On one side, you have people who think that the code generated from ChatGPT is not worthy of being copied and pasted into any respectable repository of a project or product. On the other hand, there are those who happily choose to write scripts for automating their boring tasks.
Remarkably, ChatGPT has exceeded 1 million users in the first 5 days of going public. In comparison, it took Facebook and Twitter multiple months to reach the same number of users. Its conversations have perforated most social media platforms on the internet and there are already a handful of browser extentions and web apps that are integrating with it.
Given its early stage status, it works amazingly well. Although it uses noticeably similar terminology in its responses, and, in certain occassions, when the answer is too long, the program will stop abruptly and the result would be unfinished. However, one cannot help but push the bar high by attempting to throw all sorts of questions and problems at it. Therefore, I wonder how well it would handle a puzzle stemming from a millennium problem.
What is a millennium problem?
A millenium problem (or Millennium Prize Problem) is a mathematics problem published by the Clay Mathematics Institute of Cambridge, Massachusetts (CMI). In the year 2000, the institute announced a list of seven problems that were inspired by a set of twenty-three problems organized by the mathematician David Hilbert in the twentieth century. The solution to a Millennium Prize Problem earns the solver $1 million. The Poincaré conjecture is the only one that has been solved thus far.
The P versus NP problem
Out of the six yet-to-be-solved problems, the P versus NP problem is one that still perplexes mathematicians and computer scientists even today. At a high level, it asks whether every problem that can be quickly verified can also be quickly solved by a computer. This has important implications for fields ranging from cryptography to artificial intelligence.
A problem is said to be in the class NP (nondeterministic polynomial time) if there exists a potential solution to the problem that can be verified by a computer in polynomial time. For example, the problem of determining whether a given Sudoku puzzle has a unique solution can be solved in this way, by simply checking all potential solutions and verifying that each one is correct.
On the other hand, a problem is said to be in the class P (polynomial time) if it can be solved by a computer in polynomial time. In other words, P is the class of problems that can be quickly solved. For example, the problem of sorting a list of numbers into ascending order can be solved in this way, by using a simple algorithm like bubble sort.
To summarize, the P versus NP problem asks whether every problem in NP can also be solved in P. In other words, it asks whether all problems that can be quickly verified can also be quickly solved. If the answer is yes, then it would mean that all NP problems are actually P problems, and we could solve a wide range of problems much more efficiently than we currently can. If the answer is no, then it would mean that there are some problems that are inherently hard to solve, even if we can quickly verify potential solutions. This is also applicable to other puzzles, such as the traveling salesman problem.
How does ChatGPT handle the traveling salesman problem?
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that a salesperson can take to visit each city and return to the starting city? As you can imagine, such question is especially prevalent in logistics and transportation, where planning the most efficient routes for delivery trucks or buses, for example, can greatly reduce costs.
Here's the result I got, after asking ChatGPT to suggest a solution to this problem in Python:
# Import the required libraries
import itertools
import random
# Define a function to calculate the total distance between two cities
def distance(city1, city2):
# Calculate the distance between two cities
# You can use a pre-defined function or lookup table to do this
# For the sake of simplicity, we will just return a random distance
return random.randint(1, 100)
# Define a function to solve the traveling salesmanperson problem
def traveling_salesperson(cities):
# Calculate the permutations of the cities
permutations = itertools.permutations(cities)
# Initialize the minimum distance to a large number
min_distance = float('inf')
# Iterate over the permutations
for perm in permutations:
# Calculate the total distance for this permutation
total_distance = 0
for i in range(len(perm) - 1):
total_distance += distance(perm[i], perm[i + 1])
# Update the minimum distance if necessary
min_distance = min(min_distance, total_distance)
# Return the minimum distance
return min_distance
# Define a list of cities
cities = ["city1", "city2", "city3", ..., "cityN"]
# Solve the traveling salesperson problem
min_distance = traveling_salesperson(cities)You can probably tell that the above solution is indeed very simple and naive. It uses the itertools library to calculate all possible permutations of the cities, and then iterates over the permutations to calculate the total distance for each one. The minimum distance is then returned as the result. The code might feel underwhelming at first, however it serves as a solid starting point from which you can navigate the problem better.
There are obviously much more efficient ways to solve this problem. With that in mind, I followed up my initial question by asking for a more efficient algorithm. ChatGPT suggested using the branch and bound algorithm. This uses a combination of depth-first search and pruning to quickly find the optimal solution to the problem. Here's what I got:
# Import the required libraries
import itertools
import random
# Define a function to calculate the total distance between two cities
def distance(city1, city2):
# Calculate the distance between two cities
# You can use a pre-defined function or lookup table to do this
# For the sake of simplicity, we will just return a random distance
return random.randint(1, 100)
# Define a function to solve the traveling salesperson problem using branch and bound
def traveling_salesperson(cities):
# Calculate the permutations of the cities
permutations = itertools.permutations(cities)
# Initialize the minimum distance to a large number
min_distance = float('inf')
# Iterate over the permutations
for perm in permutations:
# Calculate the total distance for this permutation
total_distance = 0
for i in range(len(perm) - 1):
total_distance += distance(perm[i], perm[i + 1])
# Update the minimum distance if necessary
min_distance = min(min_distance, total_distance)
# Return the minimum distance
return min_distance
# Define a function to solve the traveling salesperson problem using branch and bound
def branch_and_bound(cities, depth=0, path=[], total_distance=0):
# Calculate the minimum distance for the current path
min_distance = total_distance + min([distance(path[-1], city) for city in cities])
# Check if the current path is longer than the minimum distance
if len(path) >= min_distance:
return
# Check if we have reached the end of the search
if depth == len(cities):
# Update the minimum distance if necessary
min_distance = min(min_distance, total_distance)
return
# Recursively search the left and right branches
for city in cities:
if city not in path:
branch_and_bound(cities, depth + 1, path + [city], total_distance + distance(path[-1], city))
# Define a list of cities
cities = ["city1", "city2", "city3", ..., "cityN"]
# Solve the traveling salesperson problem using branch and bound
min_distance = branch_and_bound(cities)
This implementation of the branch and bound algorithm calculates the minimum distance for each path as it is being searched, and prunes the search tree when it encounters a path that is longer than the minimum distance. This allows the algorithm to quickly find the optimal solution to the traveling salesperson problem.
Weirdly enough, you'll notice that the latter script includes the traveling_salesperson method, even though it's not being used. Furthermore, in branch_and_bound we have to initialize the path with a city, otherwise we get an IndexError.
I repeated the question a few more times. Every time I would get a completely different implementation, using libraries such as numpy, sometimes with more examples and comments to justify each line of code.
Closing thoughts
It's clear that ChatGPT is a revolutionary language model, and while it has been designed to provide answers to a wide range of questions, it doesn't have the ability to solve complex mathematical problems like the P versus NP problem.
To give credit where credit is due, ChatGPT essentially co-authored this article. By extend, this goes out to everyone on the internet who has written code or published articles on the topic.