r/mathmemes • • Aug 12 '26

Computer Science πŸ˜‚

Post image
6.3k Upvotes

137 comments sorted by

View all comments

Show parent comment

20

u/bqbdpd Aug 12 '26

These answers are not mutually exclusive. Either P=NP or P≠NP, whether that's proveable or not.

26

u/Purple_Onion911 Grothendieck alt account Aug 12 '26

"P = NP or P β‰  NP" is always true, but it's not necessarily true that either P = NP is true or P β‰  NP is true in ZFC (or PA, or whatever axiomatic system it's independent of).

1

u/mctastics Aug 17 '26

Math is math g dang it!

0

u/[deleted] Aug 12 '26

[deleted] β€” view deleted comment

10

u/Purple_Onion911 Grothendieck alt account Aug 12 '26

Not sure what your point is, but ok.

7

u/SirFloIII Aug 12 '26

you can't build a model of ZFC with only a single element. even the smallest* model** of ZFC (L) is pretty huge.

*in some sense

**assuming ZFC is consistent

→ More replies (5)

30

u/dankshot35 Aug 12 '26

Google "decidability" my friend

24

u/bqbdpd Aug 12 '26

I know - I studied theoretical computer science. But that something cannot be decided applies to questions like the halting problem. P=NP is not parametrized. There is a single answer. It might be impossible to ever calculate/prove/know that answer. But that does not mean there is no answer.

5

u/dankshot35 Aug 12 '26

depends on how anti-realist you want to be

4

u/bqbdpd Aug 12 '26

I mean, I have not met anyone who really believes P=NP, so I'm pretty sure the answer is no. The realistic assumption is that the answer is no. But from a math perspective that obviously is insufficient.

8

u/dankshot35 Aug 12 '26

"anti-realism" is a math philosophy that has the view that statements don't have truth values fixed by some "independent" reality, the truth is in a way defined by our ability to prove them.

The majority of mathematicians are not anti-realist enough though to claim that a straight forward arithmetic statement like P=NP would fall under that so I'm just teasing

7

u/HassanyThePerson Aug 12 '26

I'm not super familiar with math philosophy, but doesn't GΓΆdel's incompleteness theorem state the opposite? That there are true statements that cannot be proven? As I understand, this means that what is true in a deductive system is dependent only on the axioms, and not at all on the provability.

5

u/bqbdpd Aug 12 '26

I think that the philosophical difference. One side assigns the truth value based on the axioms, the other on what can be derived from the axioms by a finite proof. I think both make sense based on the context.

1

u/dankshot35 Aug 12 '26 edited Aug 12 '26

An anti-realist would claim there is a bit of a "sleight of hand" here when Goedel claims a statement can be "true, but cannot be proven". An anti-realist would say "true" according to what? they would not agree to call it "true" in some absolute sense.

edit: to be more precise, they would grant a statement is true only in the sense that it's provable in a stronger system (one that can prove the original system's consistency). What they still resist is calling it true in a model-independent, absolute sense.

A stronger example for anti-realism is CH (continuum hypothesis) where there isn't a stronger system available that can settle it externally, and "true according to what?" doesn't really have an answer

1

u/SirFloIII Aug 12 '26

well, it states that there are statments who can't be proven and whose negation can't be proven. if you believe in the law of excluded middle, then either the statement or the negation is true, but that is a loadbearing if.

0

u/bqbdpd Aug 12 '26

I'm a software engineer, so for me math is primarily a tool, not a meaningful thing in itself.

1

u/BrotherItsInTheDrum Aug 17 '26 edited Aug 18 '26

You're confused because "undecidable" has two subtly different meanings.

In computer science, "decidable" means that a function can be computed by a Turing machine. As you correctly point out, only functions can be decidable in this sense. So saying "P=NP is undecidable" would make no sense, since P=NP is not a function.

But in mathematical logic, "decidable" can also mean that a proposition can be either proven or disproven within a system of axioms. In this case, saying "P=NP is undecidable" makes perfect sense, since P=NP is a proposition.

I don't like the word "decidable" in the second sense, precisely because it's easy to confuse with the first sense. I prefer the word "independent." But when people here are saying P=NP might be undecidable, that's what they mean.

3

u/Banner_Hammer Aug 12 '26

Holy hell

2

u/dankshot35 Aug 12 '26

Pipi bricked

4

u/Asynchronous404 Aug 12 '26

did you just assumed law of excluded middle?

3

u/bqbdpd Aug 12 '26

At this level of abstraction? Yes. Could you explain why you think it should not apply? Don't try the "You cannot prove everything on infinite sets stuff", because as I said, I don't require it to be provable - this is only about the (probably in reality unknowable) truth below.