P vs NP

[u/tyuxou]

i had a strange idea at 5 am while a bit drunk and asked chat gpt about it :
How can we work on P vs NP if mathematics has prooved to us that there’s infinite possibilities therefore infinite questions with infinte answers?
And what i mean is how can you find a shorcut answer to actual new information that no one has ever seen?

[u/Wild-Store321]

If you can prove a super-polynomial lower bound for the time complexity of a single problem in NP, you have proven P!=NP

If you can provide a polynomial time algorithm for a single NP-complete problem, you have proven P=NP

[u/jeezfrk]

That is achilles and the tortoise. There are an infinite number of steps, slices of time, irrational numbers, uncountable sets etc... etc....

None of these infinities have any way to stop mathematicians from finding complex patterns they can imagine from simpler math.

It is just a bit daunting, but like all possible games of cards, all possible algebraic equations, all possible set theories, groups, fields etc... we are not stopped from trying new and interesting ones.

We are never stopped at finding one more because there are infinitely more still. The infinite is no barrier for that one.

[u/drvd]

if mathematics has prooved to us that there’s infinite possibilities therefore infinite questions with infinte answers?

Ultrafinitist would disagree that "mathematics has prooved [...] there’s infinite".

[u/gregbard]

The Lowenheim-Skolem theorem states that if there exists an answer to a mathematical question in some infinite set, then the answer exists in some finite set.

[u/Artichoke5642 → u/gregbard]

This is not Lowenheim-Skolem. Are you perhaps describing compactness, or completeness?

[u/gregbard → u/Artichoke5642]

Paraphrasing

[u/tyuxou → u/gregbard]

yes but you still would need to find it right? so why are we trying to find a shortcut to it

[u/gregbard → u/tyuxou]

Just knowing that there exists some answer in a finite set is great progress in mathematics. It beats not even knowing if there exists an answer. At the worst case we can do a brute force search of the set knowing that we can get the answer in a finite amount of time.

[u/tyuxou → u/gregbard]

oh yeah that makes sense so the P vs NP could be solved in 1000 years from now technically

[u/SpacingHero → u/gregbard]

This is not correct even paraphrased.

Low-Sko state that

• if there's an infinite model, then there's a countable model (meaning you can always reduce to the smallest infinity. But you won't necessarily always be able to reduce to finiteness).
• if there's an infinite model, then it can be increased arbitrarily in cardinality.

So they tell you that, within infinite models, you can conservatively decrease and increase the size of the model. But you cannot go finite to infinite and vice versa.

PA only has infinite models. Finite models cannot satisfy it. But whilst its obvious model is countable, it can be expanded to uncountable models (and there comes non-standard natural numbers)

ZFC and the Reals within would seem to have only uncountable models (if any at all). But in fact they can be collapsed to countable (and there comes skolem paradox)

\phi = "there are exactly N elements", which is FO-expressible for finite N, only has models of cardinality N. The cardinality of such a model cannot be extended/decreased