P vs. NP: The Unsolvable(?) Computer Science Problem

[@Truttle1]

Keep exploring at brilliant.org/Truttle1/. Get started for free, and hurry-the first 200 people get 20% off an annual premium subscription. Also: discord.gg/EKPBjjUc65

[@joaocabralpv]

What if I don't hurry

[@Truttle1]

@@joaocabralpv then no brilliant.org for u

[@Cliffordlonghead]

@@Truttle1 hi

[@patriciafergus9929]

Turtle: Bogo sort is the dumbest sorting algorithm Quantum Bogo Sort: Exist in a superposition of holding my beer and not holding my beer

[@pyglik2296]

No, no, no, Quantum Bogo Sort is the most genius sorting algorithm, as it's always finishes after one operation!

[@kingoreo7050]

@@pyglik2296 i don’t want n! - 1 universes getting erased tho :(

[@mm552]

Miracle sorting is the best sorting algorithm, you just wait for the list to solve itself by some miracle

[@talkysassis]

By memory errors

[@LoFiAxolotl]

1974 i finished my PhD in math.... me and 14 of my colleagues were working on that problem all got matching P=NP tattoos on our arms... the amount of times i have had people ask if it's a gang of some sort... love it.. also glad that we made 0 steps in the last 50 years but the future looks promising! "AI" won't solve it but quantum computing seems to have some interesting approaches in finding solutions

[@timwhite1783]

Me and my buddies will get a P!=NP tattoo and we'll go to war.

[@larry_berry]

Thanks for an explanation. Yesterday I have been unsuccessfully trying to understand what P, NP, NP-complete and NP-hard mean for a lot of time and after watching this video I finally understood them.

[@Gutagi]

I found a beatiful proof for P=NP, which this comment is to narrow to contain.

[@Truttle1]

Put it on a webpage and send the link :)

[@web2wl00p]

that's the spirit ... at least we know now that the rest of us still has about 300 years to wait 😀

[@ThinkAboutVic]

gutagi's last theorem

[@Victor_Tran]

Here before Victor Tran!

[@thatotherandrew_]

lmao

[@rose_no]

You are incorrect. You and Victor Tran arrived at exactly the same time. This is because you are Victor Tran.

[@Truttle1]

Wait a second… is this ANOTHER Victor Tran?

[@vieilatome2257]

@@rose_no All of this is now a space-temporal paradox which because of the Édriseur formula can be reduced to a P = NP problem. It's all coming together.

[@gameofpj3286]

I think you have a small inaccuracy in the bogo sort time complexity. If you just shuffle without checking for duplicates, there isn't an upper limit, so even O(n!) isn't correct.

[@Truttle1]

I put a footnote saying it was O(n!) if it didn’t select the same shuffle more than once

[@dafoex]

I wonder how many people have asked GPTChat to solve P = NP I wonder if its ever returned something useful.

[@Joker22593]

Hello from a Complexity Theorist! If you want to make a really unique video, check out the theory behind P-Completeness, characterized simply as "problems which generally can't be solved faster using parallel computation techniques using only polynomial processors".

[@Yvant2000]

Hey ! I love seeing this kind of video where you explain a complex concept in a simple way ! Thanks a lot !

[@unchaynd7266]

On the subject of sorting algorithms, my personal favorite is sleepsort. It kind of... converts time complexity to space complexity.

[@enoua5222]

I love watching these videos despite already having a good grasp on the concepts already, you make it so fun! Plus it could probably show them to my friends in lieu of rambling on to them about cs and mathematics that i think are cool

[@CrowJustin]

Here before Victor! Also can’t help but notice that P and NP in 5:34 are from a series known as Alphabet lore.

[@StoryTeller796]

Why not use Bogo to check for every single possible wrong answer that P =NP could produce? If it produces enough of them, P != NP, if it doesn't, P = NP Oh, so that is why P = NP is so important. What if a fictional hacker character like Radical Edward from Cowboy Bebop or someone like them attempted to solve this problem. Or, what if this problem was already solved sometime in the year 2100 or around that time, maybe a few decades before, maybe a few decades after? What kind of future would humanity be living in?

[@Izzythemaker127]

Thanks for making this video. The other ones I saw never explained why NP-complete was a subcategory of NP and didn't even mention NP-hard

[@vicr123]

Never thought I'd ever see Obfuscate break down

[@sameer1321]

nooo i was 4 mins late to commenting before Victor

[@swordofkings128]

4:47 technically miracle sort is more time complex so... I threw my computer out the window.

[@felixstuber8046]

Well even if P=NP is shown, it doesn't mean our encryption breaks over night. For once it might be a non-constructive proof, so we might know there must be an algorithm to factor large numbers in polynomial time but not what it was. Also just because something can be solved in P-Time, doesn't mean it would be fast. Something like x⁹⁹⁹⁹⁹ is in P, but it still grows pretty fast.

[@Magnogen]

P = 0. Done

[@Kokice5]

Great stuff!

[@Rignchen]

4:50 hey, did you know about bogo bogo sort? it's basiclly bogo sort but worst (there's also quantum bogo sort but this one is actually the best algorythme ( =O(1) ), except it's not cause you can't use it)

[@MrCheeze]

Are impossible problems like the halting problem actually considered NP-hard? I would have said no, and that time complexity is only an applicable concept to things that are actually computable.

[@Nick-yq5uz]

Hey MrCheeze! I love your videos! The halting problem is considered NP-Hard because the timing complexity required in order to analyze a program in all instances would require at least the same time complexity as running the program in terms of the same level of Big O.

[@MrCheeze]

@@Nick-yq5uz I guess it's a matter of whether you consider it to take "infinite time" or just be impossible.

[@abd_ab3]

Your channel is soo underrated. Remember me when you're famous!

[@official-obama]

i posted a """"solution"""" to p=np that was obviously wrong, and now i deleted it

[@AV_YOUTUBE_202X]

Me too sajj

[@reinerczerwinski1326]

10:12 factorisation in in NP. but it is unlikely, that it is NP-complete. RSA could be cracked with quantum computer although there is no efficient quantum algorithm for NP-hard problems

[@MarsCorporations]

The halting problem is solvable (but with exponential storage usage, so it is not really applicable anywhere). 1. A machine has N bits of memory 2. Any program A running on this machine can only manipulate these N bits, so its internal state can be described by these N bits. 3. Another program B on another machine with 2^(N+1) bits of memory can now log "every state A has ever been in" 4. If A enters a state it has already been in before, it is proven, that A is in an infinite loop (if A is a deterministic program). 5. If A does not enter an infinite loop, it will run through a subset of all possible states and halt. 6. Both outcomes happen after a finite amount of time because machine A runs on has finite memory, and therefore a finite amount of possible internal states. 7. This proves: For any program A, running on a machine with N bits of memory, the halting problem can be solved by another program B running on a machine with 2^(N+1) bits of memory.

[@calvindang7291]

Yep - this is why the halting problem is presented assuming your machine has infinite memory.

[@MarsCorporations]

@@calvindang7291 Yeah, but then again: If you have infinite bits of memory, you also have 2^(Infinity + 1) bits of memory to store every possible state the memory can be in. So in theory, this stays solvable, even in the infinite case.

[@calvindang7291]

@@MarsCorporations In this case, the problem has "in finite time" attached to it as well, and a typical machine can still only read/write one element of memory at a time so there's no way to actually make use of all infinite memory to check.

[@MarsCorporations]

@@calvindang7291 Another Yeeeeah, but actually: Not a single algorithm utilizing infinite memory will terminate in finite time... Imagine adding every Number in an infinite list. This is an O(1) algorithm but it will take infinite time for infinite listsize. I know, I'm never happy :D

[@calvindang7291]

@@MarsCorporations An algorithm that terminates never uses infinite memory - this is correct. But if you don't know whether a program terminates or not, or how much of that infinite memory it uses, you can't know if it would terminate if you just ran it for longer (assuming the state never loops over the runtime of the program). You can't just make a program that knows the amount of memory your testing program will use, since that's unknown until you actually run said program.

[@timschulz9563]

P=NP if P=0 or N=1. Thank me later.

[@l3gacyb3ta21]

new truttle hell yeah

[@roeilustig]

A great video! Could you please make a video about APL?

[@talkysassis]

P = NP if you consider changing computers.

[@Veptis]

bogosort, improved bogosort qnd of course bogobogosort. Miracle sort etc. Esoteric sorting algorithms. I almost wrote a term paper on esoteric parsing algorithms. Which had one idea of bogoparse, which isnt that horrible. Depending on how awful you do it. And has never veen done before. Perhaps its just impossible to search for.

[@therealohead]

Where's Victor Tran at??

[@otesunki]

i ordinarily believe that P=NP because idk it just feels right

[@perodactyl490]

I think I might have been here before victor tran bit idk

[@tux1468]

Computer scientists are just lazy, I'm sure they could prove this if they tried and yet they don't. Also here before Victor Tran.

[@Truttle1]

Then you should do it then :P

[@youkofoxy]

It is a mathematics problem, not a computing problem.

[@enzoqueijao]

@@Truttle1 I don't get what's so difficult about this. Just divide both sides by P, then you get N = 1, which you can substitute to get P = 1 * P and therefore P = NP is true.

[@Valtsu0]

@@enzoqueijao you have a possible division by zero, try again

[@FullAfterburner]

They don't give away a cash prize. 37(n+n+n)=nnn for 0 < n < 10. Using the Fibonnaci Spiral/Sequence and Fine Structure Constant which Feynman uses as 1/137, we can conclude that (alpha + beta (imaginary number))/(alpha). 12th prime being 37. Golden ratio and some mathematical religion. Sin (666) + Cos (6*6*6) = -1.618.... (Golden ratio). Trying to solve a polynomial problem that is a sphere and not a circle is like trying to start a fire without oxygen. I've already submitted this stuff to Martin Bridson at Clay Mathematics Institute. They won't give any money or any recognition. 60 (12th hour) * (1/phi) = ~37. I'm pretty sure I figured something out. Appreciate the video. It's solvable. Just gotta be really really smart to figure it out.

[@schwingedeshaehers]

Are you sure, that soduku is np complete?

[@SaHaRaSquad]

The big O notation only states how the runtime behaves as the input size grows into infinity. In a standard 9x9 sudoku the input size is constant. But for the generalized problem of Sudoku of any size it's NP as it's just a slightly rewritten satisfiability problem.

[@schwingedeshaehers]

@@SaHaRaSquad the question is, if it is, or if it is to constrained, to be NP complete

[@calvindang7291]

You can't talk about time complexity at all unless you have some parameter you can tinker with. In sudoku's case, that parameter is the board size. It's a simple exercise to check that, with the problem set up properly, there is a reduction from a known NP-complete problem to sudoku.

[@joaocabralpv]

I am here before Victor Tran

[@MIITRIN]

Sorry Victor

[@Staubfinger]

I was here before Victor Tran

[@cheesuschrist300]

here before victor i think

[@Truttle1]

do an en passant

[@vieilatome2257]

after victor tran

[@i_teleported_bread7404]

Before Victor Tran.

[@mrmimeisfunny]

Before Victor Tran

[@nailuj29gaming65]

Before victor tran

[@dercoolekommentator2906]

Obfuscate is still the chad, who get all the chicks

[@kilgarragh]

when truttle dark mode?

[@SpaceByte]

who vicor

[@smile4cs]

YIIIIPPPPPPPPPPPPPPPPEEEEEEEEEEEEEEEEEEEEEEE

[@Twingamerdudes]

Before victor, idk.

[@LambdaCreates]

O(n^n)

[@lunathir]

Here before Victor Tran

[@WZen0]

Ha screw you Victor I beat you!

[@dmell]

I hope i'm before victor tran

[@mryodak]

No pee?

[@AshesOfEther]

bvt

[@jaopredoramires]

Wait this is exactly 13:37 was that on purpose

[@Truttle1]

That was a coincidence

[@jaopredoramires]

Here before Victor Tran!

[@paulfragemann3333]

I was here before Victor Tran

[@jacksmith1098]

Can you please please please make a video on golfscript?

[@Thxtnt]

Cosmos Quest Part 2, creating and saving a text file. Please do this that way you can suffer just like I've been suffering for the past 45 hours trying to do this