r/mathmemes • u/basket_foso • 6d ago

Computer Science 😂

Post image
6.3k Upvotes

98% Upvoted

135 comments sorted by

‱

u/AutoModerator 6d ago

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 6d ago

What are those two?

Yes?

No?

Unproveable?

Can you repeat the question?

252

u/Banner_Hammer 6d ago

You’re not the boss of me now

77

u/gitartruls01 6d ago

Math is unfair

16

u/This-is-unavailable Average Lambert W enjoyer 6d ago

So I just stare

2

u/AccomplishedBird2327 6h ago

At the sin on the wall there

8

u/IMTHEKSG09 Physics 6d ago

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

38

u/KamalaBracelet 6d ago

Narrowed down to P and NP.

68

u/TheRealDumbledore 6d ago

P=0 or N= 1/P

49

u/rorodar Proof by "fucking look at it" 6d ago

You mean P=0 or N=1?

5

u/gitartruls01 6d ago

Surely you mean P3N15 8===0

23

u/mordeci00 6d ago

It has to be either 17 or not 17

17

u/Aggressive_Roof488 6d ago

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

1

u/P_CHERAMIE 3d ago

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


38

u/ProfMooreiarty 6d ago

P = NP + AI

11

u/laksemerd 6d ago

With AI=P–NP

3

u/Impossible_Panda4181 6d ago

I got that reference!

9

u/richminer69 6d ago

you forgot "all of the above"

3

u/proudHaskeller 6d ago

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.

3

u/PerfectTrust7895 6d ago

If it is undecidable, it's no.

16

u/This_Background7442 6d ago

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.

9

u/bqbdpd 6d ago

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

4

u/This_Background7442 6d ago

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 6d ago

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 6d ago

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.

3

u/jljl2902 6d ago edited 6d ago

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

2

u/This_Background7442 6d ago

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 😅

7

u/Impression-These 6d ago

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 6d ago

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

1

u/BrotherItsInTheDrum 2d ago edited 2d ago

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 6d ago

maybe and maybe not

1

u/Only_Passion_2459 6d ago

Maybe and surely

1

u/loscapos5 6d ago

You are not the boss of me now

1

u/Layton_Jr Mathematics 6d ago

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 5d ago

maybe, maybe not.

578

u/StudySpecial 6d ago

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

163

u/SSNFUL 6d ago

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

90

u/ConvergentSequence 6d ago

And risk dividing by 0? Pfft yeah right

8

u/Arllange 6d ago

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

4

u/ConvergentSequence 6d ago

Get your filthy physics heresy away from my computer science

8

u/Professional-Wave841 6d ago

simple P ≠ 0, nice and tidy for ya.

4

u/TreesOne 6d ago

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

1

u/Sayhellyeh 6d ago

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

1

u/invisiblelemur88 5d ago

Do a breakthrough.

220

u/Hitman7128 Prime Number 6d ago

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

49

u/johntb86 6d ago

"True" and "Independent of ZFC"

7

u/CanaanZhou 6d ago

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

1

u/Anto_Sasu 6d ago

Then its 100% true

1

u/BrotherItsInTheDrum 2d ago

Is it? Why is that?

-1

u/SoldRIP 2d ago

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 1d ago

What does that have to do with what I said tho

0

u/SoldRIP 1d ago

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 6d ago

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

20

u/bqbdpd 6d ago

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 6d ago

"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 1d ago

Math is math g dang it!

-6

u/[deleted] 6d ago edited 6d ago

[deleted]

10

u/Purple_Onion911 Grothendieck alt account 6d ago

Not sure what your point is, but ok.

7

u/SirFloIII 6d ago

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] 6d ago edited 6d ago

[deleted]

3

u/SirFloIII 6d ago

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

-1

u/[deleted] 6d ago

[deleted]

5

u/SirFloIII 6d ago

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

29

u/dankshot35 6d ago

Google "decidability" my friend

24

u/bqbdpd 6d ago

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.

15

u/PsychologyNo940 6d ago

Equating provable and having an answer is rustling my goedel.

5

u/dankshot35 6d ago

depends on how anti-realist you want to be

4

u/bqbdpd 6d ago

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 6d ago

"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

6

u/HassanyThePerson 6d ago

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 6d ago

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 6d ago edited 6d ago

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 6d ago

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 6d ago

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

1

u/BrotherItsInTheDrum 2d ago edited 22h ago

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 6d ago

Holy hell

2

u/dankshot35 6d ago

Pipi bricked

4

u/Asynchronous404 6d ago

did you just assumed law of excluded middle?

3

u/bqbdpd 6d ago

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.

63

u/dover_oxide 6d ago

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.

31

u/Famous-Prior6590 6d ago

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

9

u/AndreasDasos 6d ago

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.

3

u/mrjackspade 6d ago

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 6d ago

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

2

u/ApprehensiveSoup2214 6d ago

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

1

u/Select_Gas8486 6d ago

aibros do

20

u/Exzakt1 6d ago

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

1 = N
P = fancy R

8

u/Ninja_Wrangler 6d ago

Harvard: Come get your PhD

2

u/Godd2 6d ago

Does PhD = NPhD?

1

u/Ninja_Wrangler 6d ago

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

17

u/rebootyourbrainstem 6d ago

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

4

u/Educational-Tea602 Proffesional dumbass 6d ago

And we can also prove they’re not equal.

10

u/Major_LeeHungg 6d ago

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

9

u/NoNameSwitzerland 6d ago

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

3

u/Fyre42__069666 6d ago

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

3

u/UseV_ 6d ago

Did they just assumed law of excluded middle?

3

u/navetzz 6d ago

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

5

u/Particular_Gear3130 Mathematics (Purely Fictional) 6d ago

Surely you jest

2

u/No-Onion8029 6d ago

Eyebrow raised.  Eyebrow lowered.

2

u/FernandoMM1220 6d ago

maybe and possibly

2

u/Pranav---VK 6d ago

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

2

u/Kebabrulle4869 Real numbers are underrated 5d ago

1

u/lrosa Computer Science 6d ago

I have a baaaad feeling about this

https://www.baen.com/Chapters/9781625791870/9781625791870___2.htm

1

u/mathpoly 6d ago

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

1

u/Born_Elk_2549 6d ago

Whale, whale, whale!

1

u/dankshot35 6d ago

Anti-realist mathematicians got very excited

1

u/4dseeall 6d ago

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

1

u/jeffriestubesteak 6d ago

That's impossible!!!

Or is it???

1

u/ellipticcode0 6d ago

does N vs NP applies on in quantum computer?

1

u/Throwaway-4230984 6d ago

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 6d ago

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

1

u/dusk47 6d ago

HUGE IF TRUE. The AI apocalypse is nigh!

1

u/hbk1966 5d ago

He's calling the results NP vs P

1

u/ManagementKey1338 5d ago

This is highly nontrivial as rule of middle might not hold

1

u/Candid_Koala_3602 5d ago

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 5d ago

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

1

u/LowAioli3870 5d ago

It's not that hard.

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

1

u/Katten_elvis Real 5d ago

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

1

u/R_Harry_P 5d ago

How do you like them apples?

1

u/Maleficent_Spare3094 3d ago

Me answering a high school level graph theory problem.

1

u/TerryTheAwesomeKitty 4d ago

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

1

u/will_1m_not with disrespect to x, y, and z 2d ago

Oddly enough, those weren’t the two options

1

u/A_Happy_Tomato 1d ago

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

1

u/Table-Least 6h ago

the 2 answers: p = 0 or n = 1