1
EDIT 2023/10/06

There are objections that this is too technical to be philosophy, and while I've seen questions on this forum go far beyond what I'm asking here in set theory, computability theory, and mathematical logic broadly, I'll generalize the question to reduce the perceived burden of addressing the technical aspect.


According to ZDNet, it is an open question whether a transformer LLM like ChatGPT can facilitate the determination of a solution to the P-NP Problem. (See Can generative AI solve computer science's greatest unsolved problem? (ZDNet)) This would seem to be an attempt to mine statistical patterns of a corpus as a form of non-deterministic automated reasoning to collate a series of logical propositions that cohere to a deductively sound argument. So, the question arises as to if there is a priori justification for rejecting this particular form of generative AI as a strategy for developing a mathematical logical argument to determine an answer to the question of P-NP equivalency.


Narrowed Philosohical Question

Is it possible to use a probabilistic automated reasoning system that demonstrates awareness of syntax and semantics of natural language, such as a large language model, to help solve complex problems in the mathematical problem space of a complex problem of mathematical logic or is there an a priori reason such a strategy would fail?

9
  • 6
    Some generative AI someday, maybe, but not ChatGPT as currently designed. That thing makes trivial mistakes in arithmetic, and its basic math skills managed to worsen over time. The optimistic prognosis for ChatGPT is just "math-based search engine for academic researchers". The "a priori justification" is that its training sets are of a wrong kind and its ANN is too primitive and lacks symbolic capabilities.
    – Conifold
    Oct 6, 2023 at 0:19
  • 5
    In this context, ChatGPT can be thought of as roughly an "idea generator". Those ideas may be bad or incoherent, but they could also be good. Like with literally any other problem ChatGPT could solve, whatever output you get should not automatically be trusted or taken as true, but should be evaluated by its own merits. If you mean to include hypothetical generative AIs where we've somehow solved the problem of correctness, then that premise already assumes that we can trust the output.
    – NotThatGuy
    Oct 6, 2023 at 9:16
  • 4
    I am not sure why this is a question for PhilosophySE. You can ask this question about anything else: "Is ChatGPT going to help us solve Riemann Hypothesis?" "Is it going to help us solve climate change?" "Is it going to help us design a novel brain-computer interface?" Oct 6, 2023 at 14:55
  • 2
    @JD Proving P = NP is pretty far outside the scope of this site (even if the underlying principles of such a proof might boil down to philosophy at some point). Same for the capabilities of ChatGPT (unless you're asking specifically about some philosophy-related concern, which doesn't seem to be the case here). You're asking whether AI can solve a computer science problem (or rather whether we can trust it to do so). The closest philosophy-related question is under what circumstances we should trust the output of an algorithm, but we've answered that, and built much of society on the answer.
    – NotThatGuy
    Oct 6, 2023 at 15:17
  • 2
    When solving a hard problem it can be productive to talk to a wall. Organizing your thoughts into sentences helps you process them. Ergo, ChatGPT could be a viable strategy. You just have to not let it distract you with those pesky answers it gives. Oct 6, 2023 at 15:54

3 Answers 3

5

Speaking more generally about computer-assisted proofs, the issue with them is that if we humans are able to understand the proofs fully then the computers are just useful tools but epistemologically redundant. On the other hand, if the proofs are too long and complicated to understand then they are unsatisfying. Usually, we wish to understand why some theorem is true, not just whether it is true.

ChatGPT itself is rather limited in its mathematical capabilities, but even if a successor were able to find a proof of ¬(P=NP) it would need to be something we can understand. If the proof took the form of constructing an NP-complete problem that is demonstrably not of complexity P, that would suffice. Again, as long as the construction is not infeasible for us to understand. The difficulty with proving this, and the reason it is one of the million dollar millennium prize problems, is that it involves attempting to prove a universal negative, i.e. that there is no polynomially complex algorithm that solves some given problem.

We do allow a kind of division of epistemic labour when deferring to the knowledge of human experts, so maybe in future we would be willing to trust computer generated proofs in a more thoroughgoing fashion. But that is quite a ways away.

2
  • 5
    As long as the proof can be verified by a tool like Lean or Coq, it would be massively useful even if it can't completely be understood by humans. It would reduce the problem to the level of an experimental science: you would then have this proof as a concrete thing to investigate, kind of a mine in which to dig for ideas that humans can understand. OTOH, if the proof is not verified by anything except the AI, it simply won't be accepted. Oct 6, 2023 at 12:26
  • +1 "We do allow a kind of division of epistemic labour when deferring to the knowledge of human experts".
    – J D
    Oct 6, 2023 at 16:32
4

This would seem to be an attempt to mine statistical patterns of a corpus as a form of non-deterministic automated reasoning to collate a series of logical propositions that cohere to a deductively sound argument.

You don't need a fancy language model to this, because the grammaticalness and coherence of a sound argument (in some formal proof language) are pretty easy to determine using an algorithm. Ignoring the mention of ChatGPT, the procedure you described would work.

The issue is, most things you can prove using this "mine a corpus, then do a biased random walk through argument-space" system are profoundly boring to a human: the satisfying problems (like the Fundamental Theorem of Algebra) have "non-obvious" proofs that, in human terms, rely on some insight: the corpus-based weighting actually works against discovering these proofs, but they're too big to discover with an unbiased random walk, and reverse-corpus weighting tends to avoid proving anything at all.

So it's a viable strategy for some stuff: in fact, similar techniques are already in use in interactive proof assistants, such as Isabelle's Sledgehammer (PDF) (specifically, the MaSh machine learner). This can construct quite involved proofs for corollaries, but it wouldn't help discover the insight required to prove P≟NP.

1
  • +1 For a source of code and theory regarding ATPs.
    – J D
    Oct 6, 2023 at 16:33
2

Full disclosure: I have only quickly read the article you linked, not the original paper. That said, I find it to be the usual highly publishable, slightly dramatic, click-generating, almost-sensible-but-not-quite semi-nonsense regarding AI targeted at an audience which is not knee-deep into the topic already.

To answer your question: No, writing ChatGPT prompts is not a viable strategy for solving the P-NP problem, or any other unresolved question. There is nothing under the hood even remotely close to being related to the issue at hand.

  • The GPT "knows" nothing about any kind of semantic content regarding the questions. It has no knowledge, it knows no facts(*), it has no logic engine or anything like that. It is literally, only, simply blabbering words. "GPT" means "Generative Pre-Trained Transformer". It transforms words and sentences, it does not have the singlest clue what it is talking about. So if you ask it something related to a topic, it will - due to its unfathomably vast amount of training data - simply spew responses that have been recombobulated from some input text that was parsed during training. And not because the training stage somehow "understands" the input, but simply because a statistical algorithm concludes which words are fitting best. It is not, conceptionally, much different from the YouTube algorithm generating a list of videos on the right-hand side of your screen, to induce you to watch more.
  • Even, if by some magic intervention, or by incredibly unlikely coincidence, the GPT should indeed stumble across the correct answer (i.e. because the input data contained the answer for some reason, without any human having recognized it so far), it is impossible to extract the reasoning behind it. That is, even if the GPT says "the answer is THIS", there is no way for it to lay down a formal proof which would make us believe it. Not even that, but no matter how well you write your proofs, by design and out of principle, GPTs "hallucinate" - i.e. their answers always sound 100% sure, even if they are blatantly wrong.

To be completely untechnical: imagine a GPT like a person that's sitting in their basement, consuming some social media site (Reddit, Facebook etc.) day-in day-out, and learning everything they can about a certain topic from that, which they have zero previous experience or knowledge about, and which they never experience even once in real life. That person will soon be an expert in repeating information about that topic, and will often then repeat said information on the social media site or in real-life (i.e., the classical echo chamber). The GPT is very much like that, just with a "brain" that has zero thought processes going on, it only babbles what it heard. Its basis, though, is not just a single reddit sub, but a good high percentage of the complete textual content of the Internet as of a few years ago, in all forms (science documents, social media, forums, etc. etc.).

It is certainly still applicable to call it an AI (artificial intelligence) in the sense that the technology has become so good that it seems or simulates intelligence, so much so that lay people have a hard time disbelieving that it actually is intelligent. If you separate the concept of "intelligence" into many small parts, then you may attribute a few to them to the GPT (i.e. being able to parse and generate language, and memorize ungodly amounts of data). But aside from that, in fact, there is not a iota of intelligence in the sense required to solve any kind of problem. As of 2023, it is simply a tool for humans to wield - an awesome tool, very powerful and incredibly fascinating, but still a tool.

Some people argue that the GPT is based on ML (machine learning) with the usual aspect that we don't really know how that particular black box works. They try to imply that there could be some kind of "spark" inside the ML part of the GPT which somehow, spontaneously, creates something else altogether - a kind of AI like in the SciFi movies which suddenly is much much more than what we thought. This is not the case though. Yes, we cannot track what's going on inside the model itself (which is the reason why we cannot ever trust its arguing completely), but the scientists implementing GPTs absolutely do know how everything works. Yes, the size of the LLM within the GPT is unfathomable, but we know what it is. Basically, a humongous amount of statistics about words, nothing more and nothing less. The wonder comes from the fact that even though it's only that, we get those great results. The real achievements is the human programmers who figured out how to implement all the stuff surround it, to make it seem so real.

(*) This is slightly simplified, there are techniques to inject actual facts into the process by embedding them in prompts; this is ongoing research, and very useful i.e. to be able to upload a long document into a GPT and ask meaningful questions about that ("what statement does this document make about X"), but definitely not something about the P=NP issue which would magically lead to solving it.

1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .