News for hackers. Stuff that matters.
Re:Math writing is dull when it neglects the human dimension by js8 on Friday March 29, 2024 @01:42AM (#39861043)
IMHO it's even worse. Once we figure out P vs NP, we will understand what it means to invert boolean functions algorithmically, and all mathematics will be replaced with an automated process.

Today, most of the math is figuring out how to solve an equation, i.e. to give an algorithm to calculate the solution. We then "quantize" the algorithm to a state machine (e.g. convert reals to floats, algorithm steps to machine code), so that we could run the state machine on a computer and get a result.

However, once you know what it takes to invert boolean functions, you don't need the solution step, you can just quantize your equation (problem) directly to a SAT instance, and let the inversion algorithm do all the hard work. No (elegant and readable) math is required anymore.

So I think we better treat mathematics as a "useless" human artifact (like art or chess) rather than something of practical value.

Re:Math writing is dull when it neglects the human dimension by yau8edq12i on Friday March 29, 2024 @01:49AM (#39861067)
> IMHO it's even worse. Once we figure out P vs NP, we will understand what it means to invert boolean functions algorithmically, and all mathematics will be replaced with an automated process.

I'm sorry, but that's just naive techno-solutionism. Maybe the computer will be able to solve your syntax problems, i.e., write proofs. It will never know anything about the semantics.

Said differently. Maybe the computer will be able to give you a proof on demand on statement number 123456789 in some Gödel numbering of statements. What it won't be able to tell you is that the theorem should be called the "intermediate value theorem" and what it means. Math isn't just coming up with formally correct proofs for pre-existing statements.

I also don't see what "P vs NP" has to do with anything.

> Today, most of the math is figuring out how to solve an equation, i.e. to give an algorithm to calculate the solution. We then "quantize" the algorithm to a state machine (e.g. convert reals to floats, algorithm steps to machine code), so that we could run the state machine on a computer and get a result.

I'm a mathematician. What you wrote is just bonkers. Some parts of math are about writing algorithms to solve equations. The vast majority of math isn't.

Re:Math writing is dull when it neglects the human dimension by js8 on Friday March 29, 2024 @02:22AM (#39861204)
My point is, the need for semantics is a human construct, it's not required to solve practical problems. Practical value of MVT is that we can apply it in the process of describing a solution, i.e. an algorithm. But if you have a SAT algorithm that can somehow inherently apply a finite instance of MVT, you no longer need to know what MVT is.

And this is at the heart of P vs NP question, how to solve SAT, and once we understand that, all the math that is about solving equations (i.e. that of practical value) will become very boring. Kinda like when a game becomes solved with a computer.

(This reminds me of Chomsky and Norvig debate on the machine learning and nature of understanding. I wouldn't think I would take Norvig's position, yet here we are.)

Addendum: I am also not arguing that computers writing proofs are a necessity for this, but rather efficiently (as possible) solving SAT instances. You don't need to state a hypothesis (and thus prove it) for an infinite number of cases to solve practical problems.

I am also not judging value of math - yeah, it is fun. All I am saying it inherently has a human dimension in the sense we don't need it (assuming we have an efficient SAT solver) to solve practical problems.

Re:Math writing is dull when it neglects the human dimension by seanhunter on Friday March 29, 2024 @03:17AM (#39861446)
Most equations that can be solved can already be solved symbolically by things like mathematica or numerically by a grab-bag of numerical techniques that every maths, engineering and physics student learns at some point. You don't need to have found the solution to P vs NP to do any of that.

I think most mathematicians would say that most of maths is not in solving equations because once you get the right equations, solving them is a simple mechanical process for the most part. Most of maths is figuring out what the right equations are in the first place and proving that what you have done is legitimate.

Re:Math writing is dull when it neglects the human dimension by js8 on Friday March 29, 2024 @08:04AM (#39863015)
I disagree that converting from an equation to a solution algorithm is a straightforward process. It is very much where mathematics helps, for example just to ensure convergence of the method.

Also, the way you model reality (choose the equation) is often done with the limitations of solvability in mind.

I also disagree that maths can help you pick the right equations, just like there is no formal method that can verify whether a program specification is appropriate to the problem.

Equation (or a model) is just an infinite family of SAT problems, typically parametrized on our understanding what a "number" is. If we had a really good SAT solver, then getting a solution would indeed be a really straightforward process (just pick the number representation) of solving the instance. The same is also true for checking "legitimacy" (which I interpret as consistency) of the model - SAT solver would tell you that the instance is unsatisfiable and why. But you can never formally determine that the chosen SAT instance is appropriate model for the task at hand.

Re:Math writing is dull when it neglects the human dimension by constantcrying on Friday March 29, 2024 @06:25AM (#39862427)
None of this is true and your understanding of the subject is obviously very poor.
Re:Math writing is dull when it neglects the human dimension by js8 on Friday March 29, 2024 @08:41AM (#39863361)
Before there was AlphaGo, many top Go players believed that understanding Go is somehow special in helping us to understand the universe. The AlphaGo was a shock, because it turned Go into "just another game", which can be beaten by enough calculations on a powerful computer.

I think the mathematics is the same. Lot of its beauty we cherish, because we don't properly understand it on the "raw" level of SAT (I would write logic, but I really mean the simplest metalogic you need), which is evidenced by our lack of understanding of P vs NP. Once it is understood, the process of "doing math" will be understood algorithmically, and it will become "boring" or "dull".

But as I said, I don't think lack of universal meaning (or lack of mystique) has to detract from the beauty of mathematics.

Re:Math writing is dull when it neglects the human dimension by constantcrying on Friday March 29, 2024 @09:09AM (#39863662)
Some facts to consider:

- Polynomial problems can still require enormous computing power to the point they are unsolvable. Even if tomorrow there is an algorithm transforming every NP problem to a P problem, not all problems will be feasibly solvable. A O(n^100) Problem is still P.

- P vs. NP is about algorithmic complexity, it has no implications about mathematics being an algorithm or not.

- The most likely outcome is that P and NP are different, in which case there are zero implications on computational efficiency.

- Considering mathematical statements as algorithms has happened for a long time. Any outcome of P vs. NP has limited implications on the philosophy behind it. It just might make it somewhat better.

You just don't understand what P vs. NP is about, your posts are bizarre in the actual context of the problem statement. The implications on mathematics just aren't what you think they are.

Re:Math writing is dull when it neglects the human dimension by js8 on Friday March 29, 2024 @09:56AM (#39864158)
I think what's more fundamental than just answering P vs NP, is what exactly makes boolean functions hard to (pseudo)inverse? And it's the latter where answering (unless the answer comes from an oracle) the former will help.

And this question is crucial, because everything we can ask computers (or restated, math with real-world applications) can be rephrased in terms of finding a solution to a SAT instance. It can be a very large instance but if there is a practical way of approaching the problem, it shouldn't matter.

I think you're assuming that future computer scientists and mathematicians will continue to run (many different) algorithms, and I don't. I think there might be a single algorithm, a SAT solver, which will subsume all others.

Re:Math writing is dull when it neglects the human dimension by constantcrying on Friday March 29, 2024 @10:15AM (#39864369)
Do you not realize that SAT might just be O(2^n) at best? Even if by a gigantic miracle SAT is in P, unless there is another incredibly great miracle and it is something like O(n^3), which would almost certainly be the greatest discovery of CS, it would not replace almost any other algorithms? Simply because many of the most important ones are O(n^2) or even less.

>I think there might be a single algorithm, a SAT solver, which will subsume all others.

This is legitimately insane. You might as well hope for free energy, FTL Travel, or magic.

Re:Math writing is dull when it neglects the human dimension by js8 on Friday March 29, 2024 @10:59AM (#39864857)
> Do you not realize that SAT might just be O(2^n) at best?

Yes, but that's the worst case on all possible instances. Even with this worst case performance, there might be an algorithm that works on par with other algorithms that specialize only on certain instances. E.g. there can be an O(2^n) algorithm for general SAT which performs in O(n^(3/2)) on XORSAT. We simply don't understand the problem well enough to tell.

Also the set of worst-case instances can be vanishingly small in practice.

Re:Math writing is dull when it neglects the human dimension by constantcrying on Friday March 29, 2024 @11:09AM (#39865001)
The average case is also O(n^2).

You have a completely utopian idea about what might be computationally feasible. I don't even know what you are arguing. Certainly it is thinkable that SAT is somehow ridiculously simple to calculate, just in the same way that achieving simple and near free fusion energy is thinkable. It just isn't going to happen and speculating on it is pure science fiction.

Re:Math writing is dull when it neglects the human dimension by samatman on Friday March 29, 2024 @01:33PM (#39866764)
> Certainly it is thinkable that SAT is somehow ridiculously simple to calculate, just in the same way that achieving simple and near free fusion energy is thinkable. It just isn't going to happen and speculating on it is pure science fiction.

These are, as I'm sure you know, utterly different. Nuclear fusion is real, 'simple' and 'near free' are engineering problems. If human civilization lasts long enough, and continues to progress technologically, we'll have that, for some value of 'simple' and 'near free'.

On the other hand, the conjecture that SAT is algorithmically feasible may be disproven, and in my opinion, will be. That would be "just isn't going to happen".

Re:Math writing is dull when it neglects the human dimension by Tainnor on Saturday March 30, 2024 @10:07AM (#39875036)
> everything we can ask computers (or restated, math with real-world applications) can be rephrased in terms of finding a solution to a SAT instance

SAT is limited to propositional calculus which is far too weak for most mathematics.

Re:Math writing is dull when it neglects the human dimension by curtainsforus on Friday March 29, 2024 @10:13AM (#39864353)
Strange, for you to say this in the age of transformers. They are obviously not there yet, but it seems inevitable to me that e.g. gpt 'understands' things better than a markov chain, and that future systems will understand more.
Re:Math writing is dull when it neglects the human dimension by js8 on Friday March 29, 2024 @11:10AM (#39865012)
I know you're responding to someone else, but funny you say that. I suspect modern NN's are just iteratively solving some really large instances of SAT (similar to WalkSAT), to find a representation of a circuit that best matches a function defined on training examples (which are the constraints). So they're, unwittingly, kinda the SotA SAT solvers.
Re:Math writing is dull when it neglects the human dimension by constantcrying on Friday March 29, 2024 @06:23AM (#39862417)
>IMHO it's even worse. Once we figure out P vs NP, we will understand what it means to invert boolean functions algorithmically, and all mathematics will be replaced with an automated process.

Literal nonsense. Do you not realize that P vs. NP might have a negative outcome (extremely likely)?

>Today, most of the math is figuring out how to solve an equation, i.e. to give an algorithm to calculate the solution.

Plainly false. In basically any field proving the existence of a solution is far, far harder than calculating the solution numerically. See e.g. PDEs.

>We then "quantize" the algorithm to a state machine (e.g. convert reals to floats, algorithm steps to machine code), so that we could run the state machine on a computer and get a result.

Literally not true. Not even the assumption is right.

Re:Math writing is dull when it neglects the human dimension by js8 on Friday March 29, 2024 @09:18AM (#39863755)
> Do you not realize that P vs. NP might have a negative outcome (extremely likely)

The outcome will matter less than having an answer. And I do think it will be a negative outcome either way, because it will obsolete lot of beautiful math, and replace it with a more mechanical process.

> In basically any field proving the existence of a solution is far, far harder than calculating the solution numerically.

First of all, if you want to ascertain whether the numerical algorithm works correctly, you have to prove the existence of the solution. That's part of the (equation -> solution algorithm) conversion process.

Now, you can possibly get by without proving existence of the solution for the infinite family (and confront the numerical solution directly with reality). But doing that is more complicated than, assuming there is a SAT solver, plug the SAT instance into it and see if there is a solution (and you can get, for a finite family of instances, a similar guarantee you would get from the existence proof).

> Not even the assumption is right.

Not sure what assumption you refer to. Computers don't run algorithms (because algorithms handle unbounded input/output), computers are just a very large state machines. So you need to convert the algorithm to a state machine first. Saying "run algorithm on a computer" is just a useful figure of speech, but somewhat misleading, because it implies certain quantization.

Re:Math writing is dull when it neglects the human dimension by constantcrying on Friday March 29, 2024 @09:26AM (#39863852)
>The outcome will matter less than having an answer. And I do think it will be a negative outcome either way, because it will obsolete lot of beautiful math, and replace it with a more mechanical process.

The negative outcome will have exactly zero implications about anything. Except "turns out we were right all along" polynomial problems are just fundamentally less hard than problems you can verify the solution of in polynomial time. This has ZERO implications on anyone, except the mathematicians who prove it, who will get a price and quite a bit of academic fame. That is literally it.

>But doing that is more complicated than, assuming there is a SAT solver, plug the SAT instance into it and see if there is a solution (and you can get, for a finite family of instances, a similar guarantee you would get from the existence proof).

Even is SAT is P that doesn't imply a solution can feasibly be found. And if P neq NP, then SAT might not be P.

Re:Math writing is dull when it neglects the human dimension by js8 on Friday March 29, 2024 @10:07AM (#39864285)
> Even is SAT is P that doesn't imply a solution can feasibly be found.

It does, because in this case you also assumed that running numerical algorithm was feasible. So if your SAT solver fails to find the answer, it is either suboptimal method (because numerical method exists), or (if the instance is UNSAT) the numerical method gives you a flawed result.

Re:Math writing is dull when it neglects the human dimension by constantcrying on Friday March 29, 2024 @10:19AM (#39864413)
Do you not understand that an O(n^100) algorithm is in P, but can never be run feasibly on a computer for any non trivial amounts of n? For n=10 you are already far beyond the number of Atoms in the universe.

I don't think you have any clue what you are actually talking about.

Re:Math writing is dull when it neglects the human dimension by Tainnor on Saturday March 30, 2024 @10:14AM (#39875095)
> And if P neq NP, then SAT might not be P.

Small correction: If P != NP, then SAT definitely isn't in P. That's because SAT is NP-complete, so if it was in P, every other NP problem could be polynomially reduced to it and would hence also be in P.

Re:Math writing is dull when it neglects the human dimension by Tainnor on Saturday March 30, 2024 @10:00AM (#39874966)
That's some of the most confidently written nonsense I've read in a while.

> all mathematics will be replaced with an automated process

FOL is undecidable, so we know this is impossible.

Re:Math writing is dull when it neglects the human dimension by js8 on Saturday March 30, 2024 @02:24PM (#39877318)
I think you miss the point. I am not disputing FOL being undecidable. What I am saying is that, once we know how to solve SAT well enough, most mathematics will become obsolete (especially for applications). It will be obsoleted the similar way that symbolic solving of equations got obsoleted with numerical solving, once computers (and numerical algorithms) became prevalent enough.

Practically minded people will simply skip logical proofs and model the world directly with SAT instances. Mathematics will remain an intellectual curiosity.

In a way, I agree with the article - what makes math interesting is the human perspective and creativity. But I believe it's "worse" - taken objectively, math is actually pretty boring and there is only little depth.

Re:Math writing is dull when it neglects the human dimension by Tainnor on Sunday March 31, 2024 @01:11AM (#39881631)
> symbolic solving of equations got obsoleted with numerical solving

That never happened, symbolic and numerical mathematics coexist to this day. Cryptography, for example, relies on exact arithmetic.

On that note, good luck trying to solve problems in cryptography with "SAT instances".

Re:Math writing is dull when it neglects the human dimension by js8 on Sunday March 31, 2024 @03:21AM (#39882161)
Again, you miss the point, there will be a paradigm shift. Yes, symbolic maths still exists, but nobody is looking up a special function to solve an equation. They just plug the numbers (and the state machine approximation of the numerical operations) in the computer and numerically, the result comes out.

Symbolic/numeric is just analogy of the paradigm shift that will come to all (applied) math. Another example is in statistics, shift from parametric to non-parametric.

Cryptography.. relies on unproven belief in ETH or P/=NP or some such (in fact, cryptography has, since Caesar, relied on unproven beliefs about cryptosystems). But that's just a belief, we don't really understand how hard any of these specific problems are. Which is actually a great example of the new paradigm I am talking about, because it shows we don't need proofs (of statements about infinitely many things). We can just quantize things directly (into a state machine that actually does the crypto stuff) and be happy.

We haven't even scratched the surface of what is possible in P vs NP. In particular, CNF representation of SAT instances might be a really crappy one.

Re:Math writing is dull when it neglects the human dimension by Tainnor on Sunday March 31, 2024 @09:36AM (#39884119)
You should look up provable security. And also, while security proofs typically rely on unproven assumptions, correctness proofs in cryptography are "regular" proofs for all intents and purposes. You can't even do RSA etc. without understanding prime numbers which is impossible if you limit yourself to propositional calculus ("SAT").

> Again, you miss the point, there will be a paradigm shift. Yes, symbolic maths still exists, but nobody is looking up a special function to solve an equation. They just plug the numbers (and the state machine approximation of the numerical operations) in the computer and numerically, the result comes out.

This is false.