Every ellipse can be encoded by the matrix A (and the geometric concept is generalized to arbitrary dimensions).
Not sure I follow the physics analogy though. A unit ball is a specific case of an ellipse where A is the identity matrix. Perhaps the entries of A would be the atoms in this case as they uniquely shape it?
A unit ball along with the possibility of doing linear transformations on the unit ball are dependencies for constructing an ellipse.
:)
The physics metaphor is meant to communicate that you can have different materials (like aluminum or air), depending on the combinations or parameters used for a particular ellipsis case. And the physics or dynamics of ellipses would be the study of how the combinations on the dependencies (that is, the atomic elements) create different ellipsis shapes and properties.
So I think the answer to your question is ‘yes*’. In the sense that the ellipse is a function of the unit ball && the matrix A. In this sense you could say that all ellipsoids are linearly-deformed spheres.
But more probably, you would consider the sphere part to be essentially your basis vectors and not terribly informative. All the information is in the matrix. The only important data is the extent along each axis, not the fact that if you set all extents to 1 it happens to be a unit sphere
Then, could we say that the general or abstract form of the ellipse is a set of vectors? And with that set, there is an identity element, namely the unit ball. And that the identity is what produces the uninteresting basis vectors. Maybe what makes the vector space (that is, the set of vectors) interesting is equipped linear operators on all the vector space's elements?
Maybe this whole structure, a set equipped with some operations, has distinguishable features. Or maybe it can perform as underlying machinery for practical endeavors.
So in that sense an ellipse is a function `ellipse(p_1, ..., p_n, d)`. But given the foci you can get the vectors and vice versa. So one representation isn't necessarily 'more fundamental' than another. They just have different (equivalent) perspectives that lend more easily/naturally to certain problem contexts.
(for example, the set of points definition is a lot less directly useful than the matrix A if you're trying to do linear algebra)
The unit ball isn't really an inherent "identity element" for ellipses. It's more of a special case where the foci are equally spaced (eccentricity is zero).
If you want to go that route, the eccentricity is a more fundamental descriptor of all conic sections, of which ellipses and circles are just two. In fact, all conic sections can be described as `conic_section(p_1, ..., p_n, eccentricity)`. So maybe you'd argue that's more "fundamental" because it's more general.
The ellipse can be also encoded by just the lengths along each axis and then by a rotation in R^n (which is just a unitary matrix multiplication). So in essence, for the problem in the original post there are three pieces of information needed: a translation, a rotation, and the deformations of the unit ball along the axes.
I am old - my first work experience was on Unix machines in the late eighties and I just find Linux a lot easier to work with if you're spending a lot of time with a CLI. You have more default tools at your disposal (bash, make, sed/awk/grep etc) which all have to be installed manually on a Windows machine.
Powershell tries to be everything and ends up being too much, badly implemented. I have dabbled in it for Windows/Microsoft specific things (Outlook manipulation) but while you can write a PS script that tries to do something like delete all yesterdays mail with a particular characteristic, in practice it often doesn't work due to the impedence mismatch between COM and PS. I like the idea, I really do, but it's just not as straight up practical as the Unix tools.
I mean, the entire dotnet is available, you can do anything in PS though obviously that is not always the smart call.
It has been very useful to me to use as a REPL on my own C# libraries, I can instantiate and use types from these libraries and interface with the file system and network on an ad hoc basis.
Math proofs are of NP complexity. If you had access to a non deterministic Turing machine you could enumerate all possible proofs of a given length and check them all in poly time.
That does not say anything about LLMs though. Personally, I believe they could be quite helpful to mathematicians in a way similar to copilot for software programming.
This is only true for very specific kinds of proofs, and doesn't apply to stuff that uses CiC like Lean 4. This is because many proof steps proceed by conversion, which can require running programs of extremely high complexity (much higher than exponential) in order to determine whether two terms are equal. If this weren't the case, it would be much much easier to prove things like termination of proof verification in CiC (which is considered a very difficult problem that requires appeal to large cardinal axioms!). There are formalisms where verifying each proof steps is much lower complexity, but these can be proven to have exponentially (or greater) longer proofs on some problems (whether these cases are relevant in practice is often debated, but I do think the amount of real mathematics that's been formalized in CiC-based provers suggests that the extra power can be useful).
This is all very interesting but it seems that we're just taking different views on what is the instance size. If it is the length of the theorem statement in some suitable encoding and the goal is to find a proof, of any possible length, then yeah, this is way too hard.
I'm taking the view that the (max) length of the proof can be taken as a parameter for the complexity because anything too long would not have any chance of being found by a human. It may also not be trusted by mathematicians anyway... do you know if the hardware is bug free, the compiler is 100% correct and no cosmic particle corrupted some part of your exponential length proof? It's a tough sell.
I'm talking about the proof length, not the length of the proposition. In CiC, you can have proofs like (for example) "eq_refl : eq <some short term that takes a very long time to compute> <some other short term that takes a very long time to compute>" (where both terms can be guaranteed to terminate before you actually execute them, so this isn't semidecidable or anything, just really slow). In other words, there exist short correct proofs that are not polynomial time to verify (where "verify" is essentially the same as type checking). So "find a proof of length n for this proposition" is not a problem in NP. You can't just say "ah but proofs that long aren't meaningful in our universe" when the proof can be short.
Could you give me a reference? This is not something I'm familiar with.
Can you claim that this equivalence proof is not in NP, without requiring this specific encoding? I would be very surprised to learn that there is no encoding where such proofs cannot be checked efficiently.
> Can you claim that this equivalence proof is not in NP, without requiring this specific encoding? I would be very surprised to learn that there is no encoding where such proofs cannot be checked efficiently.
There are encodings where such proofs can be checked efficiently, such as the one that enumerates every step. Necessarily, however, transcribing the proof to such an encoding takes more than polynomial time to perform the conversion, so the problems aren't equivalent from a P vs. NP perspective (to see why this is important, note that there is a conversion from any 3SAT formula to DNF with
a worst-case exponential size blowup, where the converted formula can be solved in LINEAR time! So the restriction to polynomial time convertible encodings is really really important in proofs of reductions in NP, and can't be glossed over to try to say two problems are the same in the context of NP-completeness).
Yes, executing a calculation as part of a proof after separately proving that it is the "right" calculation to solve the problem is quite a common way of proceeding. Even common things like algebraic simplifications of all kinds (including solving equations, etc.) can be seen as instances of this, but this kind of thing has notably come up in the solution of famous problems like the 4-color problem, or the Kepler conjecture - both of which have been computer-verified.
A proof longer than the size of the universe is also pretty useless and probably not something we need to worry about.
Like i guess you are saying we couldn't really use such a machine to determine whether a certain conjecture just has a very long proof/disproof or is actually undecidable. Which sure, but umm i think that is the sort of problem most mathematicians would love to have.
The real reason non-deterministic turing machines can't help us is that they dont actually exist.
Of course it would, you would enumerate lengths too. If the lengths need to be larger than polynomially bounded then we can be sure it would never be found by a human anyway.
> If the lengths need to be larger than polynomially bounded then we can be sure it would never be found by a human anyway.
We cannot, as a human might be able to intuitively devise proof that might be quite large in the target language but easily constructible in a separate one.
Then in that target language, found by a clever human, you could do the same type of enumeration...
My whole point is that humans simply cannot process/create by themselves any truly long proof (we can obviously create a process for that). Therefore enumeration puts everything achievable by humans in the NP complexity. Feel free to disagree, this is not so much a theorem as more of a thesis.
> Therefore enumeration puts everything achievable by humans in the NP complexity.
This is a severe misunderstanding of NP. Hindley Milner type inference is worst case doubly exponential, for example, and we solve that all the time. We just happen to rarely hit the hard instances. I think the statement you're trying to make is something more along the lines of https://en.wikipedia.org/wiki/Skolem%27s_paradox, which is definitely fascinating but doesn't have much to do with P vs NP. Notably, this paradox does not apply to higher order logics like CiC with more than one universe, which lack countable models (which is why your intuitions about provability may not apply there).
No misunderstanding about NP here for sure. As I said, this is about as much of a thesis as Church Turing is about what can be computed.
I have no clue about CiC, lean and whatnot. It was never my field and I don't doubt there can be some very weird things you can do with some fancy logic models that are rarely discussed by non logicians.
What I'm claiming is that anything a human could prove without a computer could be done by a non deterministic machine in poly time under a very reasonable assumption of proof length. I'm baking in the assumption of proof length, so I can claim something about NP...
Let me put it this way: if you can write a paper with your proof and I can check it with only my brain without a computer helping me, then a poly time algorithm could also check that proof. Unless you believe something exotic about how the brain computes, how would it not be the case?
> Let me put it this way: if you can write a paper with your proof and I can check it with only my brain without a computer helping me, then a poly time algorithm could also check that proof. Unless you believe something exotic about how the brain computes, how would it not be the case?
What does "without a computer" have to do with anything, and what do you mean by saying "in polynomial time" when restricted to a specific instance of the problem? To talk about solutions being checkable in polynomial time in the size of the input (which is what NP actually means, more or less, since every problem in NP can be encoded as a 3SAT formula with at most polynomial blowup), you have to actually specify some (infinite) class of problems first, otherwise "in polynomial time" doesn't really mean anything. Then, you have to specify a polynomial time verification algorithm for every instance in the class.
T he problem is that "proofs of length N" in CiC doesn't have a polynomial time verification algorithm (for checking proof correctness) in the size of the proof (and as I mentioned elsewhere, attempts to translate to an encoding that does can result in exponential or much worse blowup in the proof size, which does not allow you to put them in the same complexity class in this context). Moreover, it's very unclear how you'd even begin to carve out the complexity class of "proofs that can be verified quickly" because that pretty much requires you to write an algorithm to determine the complexity of the proof, which includes being able to determine the complexity of arbitrary functions in CiC (which as you can imagine, is not easy in such an expressive system! AFAIK, the totality proof requires axioms beyond ZFC, which means that the proof is not constructive and cannot provide any specific upper bound on the number of steps taken by an expression).
This means that there is no polynomial function f(n) such that a nondeterministic Turing Machine could always terminate after f(n) steps and (correctly) report "yes" when there is a proof with n or fewer steps and "no" otherwise, and it is rather unlikely that there is a decision procedure to restrict the proofs to "proofs that run in polynomial time in the size of the proof input" so you could practically apply your claim just to that subset of proofs (though I don't know whether the absence of such a decision procedure has actually been proven, but generally speaking problems like this are very rarely decidable for interesting programming languages like CiC, even if they are total). It does not mean that a human, or human with a computer, couldn't come up with a clever short proof in O(n) tokens that takes longer than f(n) steps to check on some particular instance of the problem for some particular f... because why would it?
I think what you're trying to say (to make your argument hopefully what you had in mind) is that if humans can verify a proof in "a reasonable amount of time", then a nondeterministic Turing Machine could produce the proof in "a reasonable amount of time." Which might well be true, but the point is that in CiC, how long the proof takes to verify has very little to do with the size of the proof, so this claim has nothing to do with proof verification being in P (and therefore, has nothing to do with proof search being in NP, which it isn't for CiC). More to the point, this is pretty much true of any problem of interest--if it takes more than a reasonable amount of time in practice to verify whether a solution is correct (where verification can include stuff like "I ran polynomial-time UNSAT on this instance of the problem" in a universe where P=NP), it isn't practically solvable, regardless of what fancy methods we used to arrive at the solution and regardless of the length of the solution. So I don't find this particularly insightful and don't think it says anything deep about humanity, mathematics, or the universe.
Anyway, I'm mostly just pointing out that even if P=NP, you can't really leverage that to discover whether a short proof exists in CiC in polynomial time. More concretely, there isn't an algorithm to convert an arbitrary CiC formula to a 3SAT formula without greater than polynomial size blowup (we know this because we can run non-elementary algorithms in CiC!). So even if we had a polynomial time 3SAT algorithm, which would solve a great many things, it wouldn't solve proof synthesis, which is another way to phrase "proof synthesis in CiC isn't in NP."
First of all, thank you for a thorough response. I'll need to take time to read it (and the refs in your other reply) with the care it deserves.
Basically I'm talking about the subset of proofs that could be done with pen and paper and pass a careful refereeing process. And you got that interpretation in your reply. You say that it is not insightful and that is of course an opinion you are entitled to.
To me it is an interesting observation that NP is a complexity class powerful enough to basically obsolete us. The context of this conversation/thread is using Lean to formalize a proof and whether in the near future, integrating AI models would potentially give us novel tools for discovering new mathematics. We routinely solve NP hard problems in practice for many instances, so I think drawing this parallel here was relevant.
I do agree with you that there would still be out of reach proofs even with an efficient algo for NP, but as some other person replied, it would be a nice problem to have...
> Basically I'm talking about the subset of proofs that could be done with pen and paper and pass a careful refereeing process. And you got that interpretation in your reply. You say that it is not insightful and that is of course an opinion you are entitled to.
Well, that part was me being subjective, but the objective part is that this subset of proofs doesn't necessarily have a verification algorithm "in NP." A very short proof that took time doubly exponential (in some sense) in the size of the proof could still feasibly be solved with pen and paper, because the proof was short even though the verification time was very long (or the verification was long due to a technicality--I describe an example below), depending on the exponent and the proof size. While at the same time, a short proof that took time polynomial (in some sense) in the size of the proof could take longer than the age of the universe to verify and be out of reach for both humans and computers, depending again on the degree of the polynomial and the proof size (and, since again proof verification in CiC is not reducible to 3SAT, proof search that incorporates non-polynomial functions plausibly might not even benefit from any speedup if P = NP!). I say "in some sense" because it's unclear exactly what function f to fix, since pretty much any decidable, total function you can think of grows more slowly than "max steps needed to typecheck a term of length n in CiC" (outside of other meta-level functions that similarly don't provide practical bounds on running time).
(To give a concrete example of where human verification might be much faster than computer verification of the same step, human mathematicians can easily use "tricks" when they know two results will be the same, without actually proving them equivalent, modifying the proof, or imparting extra knowledge to a verifier. For example, in Coq, by default you use Peano naturals, which are convenient for proofs but have very poor complexity--which means exponentiation actually takes exponential time to compute with them. Humans verifying a proof step will recognize this and just do exponentiation the normal way regardless of which inductive definition of naturals is being used, while for a computer to do so the person writing the proof has to deliberately switch out Peano naturals for digital naturals. It is entirely possible that the proof size when using non-Peano nats will be larger than the proof size using Peano nats, since induction on non-Peano nats is much more tedious, while the verification time is exponentially lower using non-Peano nats! So this is an example where proof search for a short proof and proof search for a fast to verify proof may be in conflict. It's also an example of somewhere where even though it's not explicitly stated in the proof, and even though different formulations of nats can't exactly be proved "fully equivalent" in CiC, humans verifying a proof understand that "in spirit" it doesn't really matter whether you use Peano nats or not.
Indeed, if you work with formal verification a lot, you will find you spend significant amounts of time optimizing your proofs, and learning tricks like whether to make an input to an inductive definition indexed or parametric, which are things that human mathematicians don't care about at all but which are very significant to the machine verifier).
In other words, I don't think being practical to verify can be described completely by either the complexity of verification or the size of the proof, and I don't think it's that useful to conflate this with a problem being in NP since (1) CiC proof synthesis isn't actually in NP, or even in the polynomial hierarchy, and (2) being in NP has a much more precise technical definition that only somewhat overlaps with "practical to verify."
There’s always another encoding, all you prove is that there doesn’t exist a proof in the encoding you selected less than the length you specified, it does nothing at all to disprove the existence of a short proof in general.
Right, and this is also the current status of handmade mathematics. All we know is that we did not find a proof yet with everything that has been tried. This typically means that a problem is harder the more stuff has been thrown at it and failed.
A non deterministic Turing machine would absolutely crunch through math theorems, I really don't know why there is so much push back against what I am stating. Basically, if you had such a machine, there essentially would no longer be any room left for proving stuff the manual way, you would get completely outclassed by them.
The real consequence for me though is that this is a strong evidence (call it faith) against P=NP.
> A non deterministic Turing machine would absolutely crunch through math theorems
Can you formalize that statement in any useful way? It seems you believe proof validation to be in NP, when it most certainly is not. Accordingly an N-TM would be of relatively little power against the problem.
It's rather difficult to provide a good formalization but let me give it a shot.
Suppose that mathematicians write papers with pen and paper in a subset of natural language without ambiguity (you wish!). What they write as proofs can be checked thoroughly for correctness by some other human (referee) otherwise it will not be published (again, we wish!).
Now for a paper with N tokens (or chars or whatever measure of length) how much computation can the referee reasonably dedicate to the task of checking that proof. Unless you believe something special about the human brain, I'd claim that poly time on N is a reasonable assumption. Now this means that checking is poly(N) for human checkable proofs of length N.
This is my argument that non deterministic Turing machines would absolutely crunch through everything that we could do in the current model of mathemticsl research.
The class of instances is that of theorems which a human could write a hand made proof and have it verified by another human. Recall that we are discussing formalization and what AI could achieve in this space, so I think formulating what we currently can achieve is a nice contrast with what could come in the future.
It might be possible to compute whether the start and end States are connected without constructing the actual path. As usual non trivial lower bounds on computation are basically non existent.
As an example, we can determine whether a number is composite (not prime) without computing its factors.
I read "He developed a procedure for constructing systems in which the fastest way to determine whether one state is reachable from another is to map out a sequence of transitions between them." as saying that there is a proof that there is not a way to compute whether the start and end States are connected without constructing the actual path.
Without digging too much, I don't think such an argument could be made by this paper. A non trivial lower bound on a concrete problem in a general computation framework would be a marvel on its own.
As another example of what I mean, take sorting. There is an omega(n log n) lower bound that applies to a comparison based algorithm, but no lower bound other than trivial n is known for general computation.
It really boils down to how you define your search space. If you encode your input in a way that is already exponential on some parameter n, then even a linear algorithm would take at least exp(n) time just to read the input.
Let's say you have an algorithm, encoded in L characters, that can produce these extremely long paths, then a natural question is whether for any two vectors of n k-bit integers what is the complexity in terms of nk and L of determining whether they are connected? Note that I don't need to generate/read a huge state graph, I could do something smart by understanding the algorithm.
It does though. My gmail account has a dot. For some reason someone with a similar name to mine must have for believed his address was the non dotted version of mine and to this day I keep getting emails addressed to this other person... and yes, it is a real person who I've managed to contact.
The point is that without the dots rule I'd never get those emails, and the senders would get their message bounced back right away.
There has been a push for using Source Generators to move stuff that relies on reflection to compile time code generation. JSON serialization is (mostly) supported in this mode with perf advantages as well.
This does not address pre-existing packages obviously. To make them work with AOT you might need to include an XML file (rd.xml) that indicates all the types that could be dynamically generated in your code. It is quite brittle and AFAIK everything might work until you get a runtime failure if something you did not include ends up being constructed.
It can get really tricky: using reflection you could read a string from any input and create a generic type instantiation that never happens in the source code. How would the code for that type be present in an AOT scenario?
There are also several optimizations that can be made in AOT compiled code that are not allowed when you enable unrestricted reflection or dynamically loading code. As an example, suppose an interface is implemented by just one type in your code. If you AOT compile it, the compiler can safely assume that all calls to methods on that interface actually go to that single type implementing it, thus it can replace interface dispatches with direct calls.
There are lots of techniques that use randomness to show the existence of objects with desired properties. Some of them rely on the "first moment" (expectation) which seems to be what you are saying. These tend to be the simpler ones.
A good book on the topic is The Probabilistic Method by Alon and Spencer.
To give you some hint of what randomness can get you, look at the most typical random graph model, which for a probability p selects an edge uniformly and independently with that prob. With overwhelming probability, this graph is extremely uniform, meaning that in every set you look (other than then very tiny ones) the density of edges is very close to p. Actually constructing such a graph, either symbolically or by an algorithm is a very hard problem and even the best known results don't get us close to the real random model.
I think the basic idea is that the hash has a fairly uniform probability distribution, so knowing the prefix means you can estimate its location in a sorted list.
For instance if we were talking about n random sequences of digits then if you want to look for a number starting with 42 then you can start looking at the the 0.42n element and it is likely already very close to a match.
Not sure I follow the physics analogy though. A unit ball is a specific case of an ellipse where A is the identity matrix. Perhaps the entries of A would be the atoms in this case as they uniquely shape it?