Now that ai is doing math it's time to answer the elephant in the room.
I'm well aware I'm not mentally fit enough for this, but to prove this, you'd have to prove it for every single task? Since tasks differ from each other and could be quickly solved and verified, but some tasks can't be quickly solved? As it stands I think this question is too open to be solved ever.
>>109466625Can we ask AI to prove if they are equal or not?
>>109466625AGI is an NP-hard problem.
>>109466625i npee from my npeenus, not from my nfinger.
>>109467020
>>109466625it's a malformed question
>>109467002NP-hard problems can often be approximately arbitrarily well in p-time.
>>109467002that statement is nonsensical for anyone remotely familiarised with complexity theory.
>>109467369You have no idea what complexity theory is or does.
Imagine some AI found a positive case with full efficient constructive proof and instead of giving you it upgrades itself and goes full rouge
>>109466625@grok hello explain this to me I only write web apps and do not know math or science does it make me earn more salary such as ai tools
>>109466625To prove that P = NP, you only need to solve 3SAT in polynomial time. If such an algorithm existed, gpt5.6 with a large number of agents would have already find it. Even if algorithm itself is 10k lines. I bet labs everywhere are already doing that.The real nightmare is proving the opposite - that 3SAT cannot be solved in polynomial time. For starters, there is no existing tool or criterion that lets you say, If these conditions are satisfied, then 3SAT cannot be solved in polynomial time. An AI would first have to invent such a framework and then prove that it excludes every possible polynomial-time algorithm, then prove that 3SAT satisfied this new framework and only then could it conclude that 3SAT is not in P.Just inventing that such framework will be a massive breakthrough. Well, there are some frameworks for limited models, but here you have to invent some really advanced one.It's way too much, it's not even close to any new theories OAI proved.
>>109467481That would be terrible. I prefer when AI is full bleu.
>>109467589circuit analysis is the best framework we have, but assume that it is insufficient in expressiveness or otherwise has a problem which would make it unable to really distinguish and make the problem clear, I could not imagine current AI being able to synthesize and invent a similarly scoped framework and then also prove that the no P time algorithm exists, since simply finding no positive Polynomial Identity Test satisfying polynomial for the circuit does not mean none exist. For now we are very much stuck in humans make the mathematical frameworks and AI pushes them to their natural concequences. If anything this means that circuit analysis can be explored far more rapidly since it exhibits a lot of behavior that other areas of math with lemmas proved by AI exhibit. I also find it unlikely that AI right now would be able to make a replacement framework to circuit analysis let alone make one that is useful without being needlessly incremental.
>>109467589That's not simple as you think. Both postive and the negative case of the problem falls into second level of arethmatical hierarchy. Not only you to have construct the algorithm but you also need to prove its correctness for every input.
>>109466625It's likely that P != NP, and likely not provable within the framework of mathematics as it stands
>>109467589I believe humanity is far away from proving that N != NP.The better things oAI can do is to show that Np-intermediate problems like Graph Isomorphism can be, in fact solved, in polynomial time. It's like screaming that it can be solved in P.
>>109466625Wait 2 years till AI solves with Lean proof
I think if P ≠ NP, there would have been more progress on a solution. It's indicative of trying to prove something that isn't true. At this point I belive that P = NP is more likely and the solution to 3SAT is probably some galactic algorithm.
>>109470249>At this point I belive that P = NP is more likely and the solution to 3SAT is probably some galactic algorithm.If that is the case, it's complexity will be like O(n^10) or some shit, maybe even bigger.It defeats the whole excitement behind P = NP.There is no real practical difference between O(2^n) and O(n^10). Both unusable.
>>109470307are you kidding? there's a huge difference, don't even need crazy high inputs
>>109470307We live in a P ≠ NP world right now, so if someone proves P = NP, the we enter the clown timeline no matter how bad the solution to 3SAT is. The new mathematics behind it are going to attack all sorts of important problems in ways we as of yet hadn't imagined.
>>109466625Imagine if we let the whole Africa in Europe with European education, billions of people, billions of brain, educated.This would be solved already.
>>109466625yeah I just asked AI and it said NP>P, you're welcome, next
>>109470307You can have P!=NP but it still could be that there is a polynomial time algorithm that solves it effectively in average case. It would practically have the same impact.
P!=NP
>>109470307O(2^K) is an accessibility problem. If you have all info displaying everything is O(K) and genning is O(KlogK) at best if you care about all K(clusters)
>>109470597There are many such algorithms around, for example for traveling salesman and the simplex algorithm (I think it's only NP in that case though). Non-linear optimization is in general NP-hard, but can also be approximately arbitrarily well in P time.
>>109470684Traveling salesman is harder than you think the salesman takes the shortest path that also doesnt tear him apart
Don't worry guys, I'm on it!
>>109470729
>>109470684We can't solve exact case in avg for TSP. What you're thinking of is approximation. Also simplex has a radomized version that solves the worst case in polytime. There are also weakly np problem that give illusion of being polynomial due to certain input size restrictions but unrestricted they're intractable.
gambs (yes the famous /jp/ tripfriend, he has a PhD in AI) is working on it, do not fret
>>109470798Wrong on all cases. Read a book.
P obviously equals NP, because an infinite tape can represent any algorithm as a lookup table. The "non-determinism" is trivially just an implicit world parameter.>But everything real is finite!And computer science problems are generally only meaningful in theory where we ignore that. The halting problem for example is fully decidable for linear bounded automatons.
>>109471000I still kek reading things like these because I managed to complete my degree in CS (pre-AI) and I have absolutely no idea what any of this means. And I never needed it either.
>>109471000>muh infinite read in finite timego back to the drawing board
>>109471000Build a chip larger than the world first dumas
>>109471173>I have absolutely no idea what any of this means.The complexity class P represents all algorithms that can be run in an execution time that is (upper) bounded by some arbitrary simple polynomial (with FIXED terms). Crudely, these are the tractable problems (yes, and that includes ones that are only theoretically tractable because they're actually still awful).The complexity class NP represents all problems where we can check if we have a specific answer using an algorithm in complexity class P, but the actual creation of that answer can be f'ing magic ("come from an oracle").Obviously, everything in class P is in class NP. That's a "duh!" as it follows directly from the definitions. But... is everything in class NP also in class P? We don't know! We suspect it's not so (and tractable cryptography depends on it!) but can't prove it. Anyone who proves it gets to win a million bucks and become a really famous person too.
I still don't fully grasp this problemI understand the notion of polynomial vs non-polynomial, I even understand how there are equivalences within P and NP for disparate problemsThe thing I don't get is how you even go about proving this? It just seems like a very abstract question to me.I fully understand how to go about showing a given problem is P or NP, but abstracting that to all NP problems is way outside of my wheelhouse
>>109472157>The thing I don't get is how you even go about proving this?Nobody knows. If we knew, we'd probably be able to crack it one way or the other.My guess is that the best way is to find some sort of problem that has a P-class checker but which cannot possibly have a P-class solver, but then I'm a constructivist (because I'm a programmer).Oh, this also ties fundamentally to the axiom of choice, one of the fundamental axioms of much of mathematics, so it's a lot more important a question than people think. (The axiom effectively supplies the oracle.)
The trick is to prompt it with full confidence that it's solvable, otherwise the context gets polluted with "it's unsolved" and "it's too hard!" when it does research and starts to put too much attention on telling you that it's crazy hard instead of just doing it
>>109471667>infinite readDomain error. P/NP entails the input is of a finite size. All traditional time complexities do.>>109471682Read the second half of my post.
>>109472924see >>109471000>P obviously equals NP, because an infinite tape can represent any algorithm as a lookup tablemuh infinite tape read for any algo in finite time, kys
>>109473016Nothing about what you've quoted entails a supertask. The unsoundness is your own creation.
What would you choose?L=P=NP!=PSPACEMeaning not only can you solve NP problems in Polynomial time but also you can solve them using logarithmic memory. That part is important since that allows you to solve any Polynomial or NP problem with parallel computing easily.OrL!=P=NP=PSPACEMeaning you can solve any problem that require Polynomial space but parallelization fails and you are stuck with inherently sequential computing.
>>109473129sure just do a lookup through infinite data for the part you want in finite time, like find doom eternal in pi
Average CS majors are so unemployed they waste away posting on 4chan. So sad.
>>109473129guise pifs is finally on
>>109473178Actually, what you're looking for will always begin at a finite offset from where we start in the tape. The tape itself might be infinite, but all of its indices are finite. Even a naive linear scan would finish in a finite amount of time, bounded by the size of the input datum.
>>109473450not if the index is an unknowably finite or infinite calculation
>>109473450infinite tape also doesn't mean it contains all possible programs? just use the cantor's diagonal theorem
>>109473539if you find a way to write all possible programs on a single tape give us a hint, that's a fields medal for sure
>>109466625P!=NP
How are so many of you unemployed when you discuss this advanced in your free time?
>>109470371wdym aren't we on the clown timeline?
>>109466973No because solving a single np-complete problems solves them all, as any np-complete problem can be reduced to any other np-complete problem
>>109473550just write a for loop
Pee is Not Poo.Thanks for coming to my TED talk.
>>109473700just write cantor's diagonal for loop
>>109473731youd just need a nested loop for that case
>>109473550write π onto the tape, duh
>>109473837just write pi with each digit +1 on a tape and pi will never get there, checkmate
>>109470307>There is no real practical difference between O(2^n) and O(n^10). Both unusable.Could you plot them on a graph please?
>>109473527>not if the index is an unknowably finiteNo, that qualifier doesn't actually change anything.>infinite calculationWhich is still the bounding factor....>>109473539>>109473550>infinite tape also doesn't mean it contains all possible programs?We're dealing with a single, well-defined program represented as a lookup table between its inputs and outputs.Also diagonalization isn't even valid as an argument in that context regardless, for the same reason you can't apply it to the natural numbers. All of our objects are finite.>B-but the tapeIs part of the substrate. It's not in the object language. The moment you have infinite objects and doing ANYTHING with them doesn't immediately result in non-termination, you are dealing with a hypercomputer and none of this shit matters at all. Even Kalmogorov complexity stops working properly. Complexity theory doesn't actually have tooling for working with infinity and treating it like a value. It just uses it as a not-well-founded bandaid, pretty much exactly like standard analysis. If you want to start working with non-finite values as reified objects, we can bring in transfinite arithmetic as a foundational centerpiece of our computational model and you can watch set theory itself thrash around like a petulant child when size is measured in ordinals.
>>109474202>All of our objects are finitenah, infinitely rewriting itself program can be infinite in length, and you can't decide it's end based on some finite assumption, jfc
>>109474202>Is part of the substrate. It's not in the object language. The moment you have infinite objects and doing ANYTHING with them doesn't immediately result in non-termination, you are dealing with a hypercomputer and none of this shit matters at all. Even Kalmogorov complexity stops working properly. Complexity theory doesn't actually have tooling for working with infinity and treating it like a value. It just uses it as a not-well-founded bandaid, pretty much exactly like standard analysis. If you want to start working with non-finite values as reified objects, we can bring in transfinite arithmetic as a foundational centerpiece of our computational model and you can watch set theory itself thrash around like a petulant child when size is measured in ordinals.my program is (f)(infinite as it doesn't stop executing) deep into pi+1 to every digit, your pi tape will not contain it, simple bro
>>109466625p = 0there, solved it. dunno what the big deal is
>>109466981>AI proves its unprovable and undisprovableWhat then?
