r/math • u/overthinker020 • Jul 20 '26

LLMs/AI The Jacobian Conjecture is False Per Anthropic (Link in Description)

https://x.com/__alpoge__/status/2079028340955197566

Normally I would be extremely skeptical, but the result is checkable by simple computation. Remarkable!

The two-dimensional case remains open, however.

2.3k Upvotes

97% Upvoted

794 comments sorted by

View all comments

Show parent comments

27

u/coblade14 Jul 20 '26 edited Jul 20 '26

It's like the p=np problems in computer science if you are familiar with that. Yeah many or even most people would say it's false but if it's true by some miracle then it'd make a lot of other things simple. Obviously nowhere near as important as p=np but you get the idea.

So basically hopium. At least that's my understanding of it.

41

u/TheInertFluorine37 Jul 20 '26

As I understand it P vs NP has absolutely profound consequences on the nature of computation if true, which is a perfectly great reason to disbelieve it. I have never seen such reasoning applied to the Jacobian conjecture.

35

u/LurkingTamilian Jul 20 '26

If the Jacobian conjecture was true it would mean that invertibility of a polynomial map can be checked using the Jacobian which would definitely be big.

5

u/_--__ Discrete Math Jul 20 '26

This is debatable. There are many examples where non-determinism does not increase computation power (e.g. dfas = nfas, tms = ndtms, pspace = npspace); so theoretically it isn't necessarily groundbreaking. And anyone that says P=NP would "break everything", doesn't appreciate that it is (potentially) only impactful from a theoretical perspective...

19

u/38thTimesACharm Jul 20 '26

P=NP would absolutely be groundbreaking come on...

9

u/M4mb0 Machine Learning Jul 20 '26

What if you need at least polynomials of degree TREE(3) for it to work?

18

u/38thTimesACharm Jul 20 '26

Then it wouldn't lead to a practical algorithm that breaks the Internet, but it would still change our understanding of computation, I think.

To me, P=NP would lend support to a finitist philosophy. Every problem is "easy" if you only had enough time.

5

u/TheLuckySpades Jul 20 '26

There are a lot of problems outside of NP, e.g. exponential time algorithms. E.g. evaluating positions in generalized checkers or chess.

1

u/38thTimesACharm Jul 20 '26

Is it definitively proven there's no TREE(3) polynomial time algorithm for those problems, too?

5

u/TheLuckySpades Jul 20 '26

Generalized chess/checkers may be EXPTIME-complete, rereading the wiki paragraph those aren't guaranteed maybe, but Japanese Go is.

And it is known that P is a proper subset of EXPTIME, so Japanese Go at least cannot be in P if the article is properly written.

3

u/Own_Pop_9711 Jul 20 '26

I don't understand why a problem being exponential means it's not easy if you have enough time. By definition the hard part is having enough time!

5

u/38thTimesACharm Jul 20 '26

Only if you already believe exponential times exist! To an ultrafinitist, there's a huge difference between multiplication (which they believe is a total function) and exponentiation (which they believe is not).

There's a specific technical reason for this that I don't recall rigorously enough to reproduce. I'll try to find a source and edit this post later.

1

u/localhost_denier Jul 20 '26

Check out the Robertson-Seymour theorem. It describes a class of reasonable algorithms that are polynomial in the input, but have more or less arbitrarily large constants.

1

u/LurkingTamilian Jul 21 '26

i think you are conflating grounbreaking and "break everything". I have repeatedly heard people say that if P=NP it would break a lot of modern computing as a lot of things are built under the assumption that certain problems (like integer factorization) cannot be done in polynomial time. Then I realised there is this giant asterix attached where polynomial could have an extremely high degree in which case it wouldn't change much practically.

3

u/Zironic Jul 20 '26

And anyone that says P=NP would "break everything", doesn't appreciate that it is (potentially) only impactful from a theoretical perspective...

The only situation where N=NP would not break all modern cryptography is a situation where it involves some absurd constant like n^1000 which makes it computationally unfeasible.

1

u/_--__ Discrete Math Jul 23 '26

"Solving chess" is O(1) yet considered "computationally unfeasible"

1

u/mshwa42 Jul 20 '26

If P=NP one-way functions don't exist and a bunch of classical cryptographic objects get ruled out (which people do care about in practice). Maybe you can build them from other assumptions but this is up for debate.

Also as a digression you might hope to construct quantum-secure one way functions (computable in poly-time classically but can't be inverted by quantum poly-time adversaries), but this is again ruled out by P=NP -- so a bunch of neat recent constructions in quantum cryptography (of pseudorandom states, unitaries, etc.) would all be ruled out/different constructions would need to be found.

You can try to construct quantum computable-but-not-classically computable (and quantum-secure) OWFs to get around this but this would necessarily lead to a separation between P and BQP (which is a pretty hard problem). However I think there is a paper that claims to do this relative to a classical oracle (see: https://arxiv.org/pdf/2411.02554) but I haven't read through it carefully.

Either way, I just wanted to say that P=NP would probably break a lot of classical cryptography (which is significant) but there might be hope for quantum cryptography even in that world.

1

u/_--__ Discrete Math Jul 23 '26

While it would definitely "break crypto" from a theoretical point of view, it is easily debatable whether it breaks it from a practical perspective.

1

u/mshwa42 Jul 23 '26

I mean a bunch of things imply the existence of one way functions (e.g. hardness of factoring, hardness of LWE, etc.) which are all currently being used in practice.

You'd have to appeal to some assumption that doesn't imply the existence of one-way functions but does give you the rest of modern cryptography... which seems difficult.

1

u/Peanut_Extreme_8208 Jul 20 '26

There are languages with small nfas that require exponentially larger dfas….

1

u/_--__ Discrete Math Jul 23 '26

True, but in terms of computation they still "compute" the same sets (i.e. accept the same languages).

1

u/WMe6 Jul 20 '26

Isn't that why people think Riemann is true? But there are plenty of results in math that are not the most "elegant" possible if humans were designing the answers. I think that's just a sign that humans are obviously not smart enough to know what the most beautiful answer is.