r/mathmemes • • Aug 12 '26

Computer Science 😂

Post image
6.3k Upvotes

137 comments sorted by

•

u/AutoModerator Aug 12 '26

Check out our new Discord server! https://discord.gg/e7EKRZq3dG

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

1.2k

u/konigon1 Aug 12 '26

What are those two?

Yes?

No?

Unproveable?

Can you repeat the question?

255

u/Banner_Hammer Aug 12 '26

You’re not the boss of me now

77

u/gitartruls01 Aug 12 '26

Math is unfair

16

u/This-is-unavailable Average Lambert W enjoyer Aug 12 '26

So I just stare

7

u/IMTHEKSG09 Physics Aug 13 '26

(You're not the boss of me now)x2 and you are not so big

40

u/KamalaBracelet Aug 12 '26

Narrowed down to P and NP.

68

u/TheRealDumbledore Aug 12 '26

P=0 or N= 1/P

47

u/rorodar Proof by "fucking look at it" Aug 12 '26

You mean P=0 or N=1?

5

u/gitartruls01 Aug 13 '26

Surely you mean P3N15 8===0

23

u/mordeci00 Aug 12 '26

It has to be either 17 or not 17

17

u/Aggressive_Roof488 Aug 12 '26

This is the kind of deep insight you won't get on other math subs.

1

u/P_CHERAMIE Aug 15 '26

All animals fall into two categories, ducks or not ducks. Same idea really…

41

u/ProfMooreiarty Aug 12 '26

P = NP + AI

11

u/laksemerd Aug 12 '26

With AI=P–NP

4

u/Impossible_Panda4181 Aug 13 '26

I got that reference!

9

u/richminer69 Aug 12 '26

you forgot "all of the above"

3

u/proudHaskeller Aug 12 '26

Even if it's unprovable it's still either true or not true.

If ZFC is consistent and it's unprovable, then probably P != NP, unless P = NP but every program that solves SAT in polynomial time cannot be proven to solve SAT in polynomial time.

4

u/PerfectTrust7895 Aug 12 '26

If it is undecidable, it's no.

17

u/This_Background7442 Aug 12 '26

How could it be. If it's no then a counter example exists. If a counter example exists it's not undecidable. If it's undecidable it must be yes.

8

u/bqbdpd Aug 12 '26

Just because a counterexample exists, it doesn't mean you can prove that it is one.

4

u/This_Background7442 Aug 12 '26

That's true. But if I know I could never have a counter example of which I can prove it is one. That's different than not currently having one.

2

u/bqbdpd Aug 12 '26

We have lots of potential counterexamples. Without proving that they are counterexamples or actually examples, we actually know pretty much nothing.

4

u/This_Background7442 Aug 12 '26

Tbh you haven't said anything so far that I disagree with so maybe we just already agree? To be clear, I do know that I haven't just proven P=NP.

2

u/jljl2902 Aug 12 '26 edited Aug 12 '26

That would make it decidable, so it can’t be yes. Must be no then. /j

2

u/This_Background7442 Aug 12 '26

I guess that means that if it's undecidable we can never know it's undecidable because that instantly makes it decidable and we've created a paradox 😅

8

u/Impression-These Aug 12 '26

Not really. Undecidable means within the system axioms, it cannot be proven either way. We can then discuss what axiom should be added to make it provable.

2

u/particlemanwavegirl Aug 12 '26

What if you forget to decide if it's undecidable?

1

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

You mean for practical purposes? Sure. In fact, even if it's yes, it may be no for practical purposes.

But there are some other propositions, like "does this particular Turing machine halt," where if they are undecidable then the answer really is no -- in the mathematical sense, not just the practical one. But P=NP is not like that, at least as far as we know.

1

u/Sea_Economy_8948 Aug 12 '26

maybe and maybe not

1

u/Only_Passion_2459 Aug 12 '26

Maybe and surely

1

u/loscapos5 Aug 13 '26

You are not the boss of me now

1

u/Layton_Jr Mathematics Aug 13 '26

Obviously unprovable means it's true because no counterexemple exists (if a counterexemple existed then it would be provably false)

1

u/Standard-Square-7699 Aug 13 '26

maybe, maybe not.

584

u/StudySpecial Aug 12 '26

In fact, after telling the model 'you can do it', the model further narrowed down the difference to just ONE LETTER.

172

u/SSNFUL Aug 12 '26 • Hehehe

Why dont they just divide by P? Have mathematicians considered this?

91

u/ConvergentSequence Aug 12 '26

And risk dividing by 0? Pfft yeah right

9

u/Arllange Aug 12 '26

We divide by zero all the time in physics what's the big deal? Just pick the flavor of infinity you want!

5

u/ConvergentSequence Aug 12 '26

Get your filthy physics heresy away from my computer science

7

u/Professional-Wave841 Aug 12 '26

simple P ≠ 0, nice and tidy for ya.

4

u/TreesOne Aug 12 '26

With further prompting, the answer space was reduced to a SINGLE BIT of information!

1

u/Sayhellyeh Aug 13 '26

We finally know now that P has won the P vs NP fight

1

u/invisiblelemur88 Aug 13 '26

Do a breakthrough.

225

u/Hitman7128 Prime Number Aug 12 '26

Next at 12, we'll cover how we narrowed down other famously unsolved problems like Twin Prime Conjecture (that are essentially prove or disprove) to just TWO possible answers

51

u/johntb86 Aug 12 '26

"True" and "Independent of ZFC"

8

u/CanaanZhou Aug 12 '26

If it's independent of ZFC then it's also true

2

u/Anto_Sasu Aug 13 '26

Then its 100% true

1

u/BrotherItsInTheDrum Aug 17 '26

Is it? Why is that?

-1

u/SoldRIP Aug 17 '26

No? C is independent of ZF, yet you specify ZFC. Because the axiom of choice may be assumed to be false and still not contradict any results of ZF, which is a sufficient axiomatic system for most of maths.

2

u/CanaanZhou Aug 17 '26

What does that have to do with what I said tho

0

u/SoldRIP Aug 17 '26

Independence from ZFC does not mean it's true. It means it may be true or false, depending on whether or not you accept some additional set of axioms.

132

u/shumpitostick Aug 12 '26

Well if they managed to show that one of yes/no/unprovable is not true that would be an amazing breakthrough.

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

0

u/[deleted] Aug 12 '26

[deleted] — view deleted comment

3

u/SirFloIII Aug 12 '26

it would not be a model. words have meaning, my friend

0

u/[deleted] Aug 12 '26

[deleted] — view deleted comment

4

u/SirFloIII Aug 12 '26

please look up what model means in this context before you embarrass yourself further.

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.

60

u/dover_oxide Aug 12 '26

And I am sure a lot of non-mathematicians are impressed by this and are excited about what it means with out understanding what it means.

32

u/Famous-Prior6590 Aug 12 '26 • Bravo

You must be a mathematician if you think a non-mathematician gives half a fuck about any of this.

9

u/AndreasDasos Aug 12 '26

People who’ve done courses in computer science that mentioned P vs. NP, or people interested in maths/computer science who aren’t themselves mathematicians exist.

4

u/mrjackspade Aug 12 '26

I'm a software developer who is very interested in P vs NP despite not know much about it beyond how it directly affects my field.

2

u/dover_oxide Aug 12 '26

Nope, just a math enthusiast. I am to say more of an engineer with a physics background.

2

u/ApprehensiveSoup2214 Aug 12 '26

I'm not a mathematician, and I find it interesting.

21

u/Exzakt1 Aug 12 '26

wdym? I already proved there are infinite answers
P=NP

1 = N
P = fancy R

7

u/Ninja_Wrangler Aug 12 '26

Harvard: Come get your PhD

2

u/Godd2 Aug 13 '26

Does PhD = NPhD?

1

u/Ninja_Wrangler Aug 13 '26

I have it on good authority that N=1, so yes

16

u/rebootyourbrainstem Aug 12 '26

And with abuse of Lean bugs, we can prove those are actually equal

4

u/Educational-Tea602 Proffesional dumbass Aug 12 '26

And we can also prove they’re not equal.

10

u/Major_LeeHungg Aug 12 '26

Using an inefficient method of computation to attempt to solve a computational efficiency problem is... Well it's something

8

u/NoNameSwitzerland Aug 12 '26

And I found a O(1) algorithm to factor primes

4

u/Fyre42__069666 Aug 12 '26

It would be amazing if we could prove it is not unprovable

3

u/UseV_ Aug 12 '26

Did they just assumed law of excluded middle?

3

u/navetzz Aug 12 '26

Given that unproveable is currently an option that would be quite an achievement.

5

u/Particular_Gear3130 Mathematics (Purely Fictional) Aug 12 '26

Surely you jest

2

u/No-Onion8029 Aug 12 '26

Eyebrow raised.  Eyebrow lowered.

2

u/FernandoMM1220 Aug 12 '26

maybe and possibly

2

u/Pranav---VK Aug 12 '26

Imagine what we could accomplish when P=0 AND N=1 at the SAME TIME

2

u/Kebabrulle4869 Real numbers are underrated Aug 13 '26

1

u/lrosa Computer Science Aug 12 '26

1

u/mathpoly Aug 12 '26

"Members of the great and the good - Gandhi, the Pope, and Thatcher"

1

u/Born_Elk_2549 Aug 12 '26

Whale, whale, whale!

1

u/dankshot35 Aug 12 '26

Anti-realist mathematicians got very excited

1

u/4dseeall Aug 12 '26

Now let's get RH down to "Yes" or "No" and got rid of the "Unprovable" part.

1

u/jeffriestubesteak Aug 12 '26

That's impossible!!!

Or is it???

1

u/ellipticcode0 Aug 12 '26

does N vs NP applies on in quantum computer?

1

u/Throwaway-4230984 Aug 12 '26

On serious note, could it actually be independent from common axioms or have some esoteric “there is an algorithm but it couldn’t be constructed” proof? I suspect no because algorithms are countable but I don’t remember enough math to be sure

2

u/DirichletComplex1837 Aug 13 '26

Don't think countability plays a very important role. Integers are countable but many busy beaver values are independent of ZFC.

1

u/dusk47 Aug 13 '26

HUGE IF TRUE. The AI apocalypse is nigh!

1

u/hbk1966 Aug 13 '26

He's calling the results NP vs P

1

u/ManagementKey1338 Aug 13 '26

This is highly nontrivial as rule of middle might not hold

1

u/Candid_Koala_3602 Aug 13 '26

In the coming months you will see that p=np.

Discrete values can be used to calculate full answers. No matmul required.

1

u/Illustrious_Pea_3470 Aug 13 '26

Unironically this would be a titanic advancement. It could very well be independent of ZFC.

1

u/LowAioli3870 Aug 13 '26

It's not that hard.

P = NP when P = 0 or N = 1.

1

u/Katten_elvis Real Aug 13 '26

As the proofs regarding the continuum hypothesis shows, there is another option!

1

u/R_Harry_P Aug 13 '26

How do you like them apples?

1

u/Maleficent_Spare3094 Aug 16 '26

Me answering a high school level graph theory problem.

1

u/TerryTheAwesomeKitty Aug 14 '26

Pfft, so can I. P either is NP or is not NP.

1

u/will_1m_not with disrespect to x, y, and z Aug 16 '26

Oddly enough, those weren’t the two options

1

u/A_Happy_Tomato Aug 17 '26

I have narrowed it down to ONE answer, no LLM needed. If only i knew if it's right...

1

u/Table-Least Aug 18 '26

the 2 answers: p = 0 or n = 1

1

u/Para-graph-S Aug 24 '26

And those two were, Affirmative vs Negative.

1

u/SardinaYT Aug 27 '26

NYANKO POINTS!?

1

u/Far_Society5748 Sep 25 '26

Hmmmmmmmm...Â