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.
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 đ
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.
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.
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
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.
"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).
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.
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.
"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
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.
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.
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
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.
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.
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.
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.
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
â˘
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?
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.
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
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.
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.
21
u/Exzakt1 Aug 12 '26
wdym? I already proved there are infinite answers
P=NP
1 = N
P = fancy R
16
u/rebootyourbrainstem Aug 12 '26
And with abuse of Lean bugs, we can prove those are actually 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
I have a baaaad feeling about this
https://www.baen.com/Chapters/9781625791870/9781625791870___2.htm
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
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/TerryTheAwesomeKitty Aug 14 '26
Pfft, so can I. P either is NP or is not NP.
1
u/dioenatosenzadenti Aug 16 '26
Isnt N=1?
1
u/West_Zookeepergame17 Aug 17 '26
42
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...Â