This puzzle took me three years and required thinking in 3721 dimensions

[@AlphaPhoenixChannel]

FAQ and corrections in this comment! 1) Check out today's sponsor at brilliant.org/alphaphoenix/ for 20% off! 2) Yes, there will be a part 2 video, but no, it's not coming out next. these programming videos are monstrous to edit because they're all animations and I can't stand to look at this project anymore. hopefully the next video is something fun with the high speed camera! 3) I'd love to see more people take a crack at this! Someone on Patreon wrote a fantastic algorithm this week that could take loads of steps backwards on a glider, but apparently struggled with the larger "play button" pattern I was using. 4) A LOT of people are complaining about the complexity section, but I chose my words very carefully there. I said “NP complete is AT WORST exponential”. I also said “there’s no KNOWN algorithm” to solve NP hard questions in polynomial time. 5) AI would be awful for this problem. Neural nets also likes smooth parameter spaces, and they are good at finding “good” solutions not “exact” solutions. 6) a lot of people are pointing out that there can be more than one GoL board that leads to any given desired GoL board. On the surface it feels like this would make the problem easier, because there are more solutions to find, but it’s also this property that guarantees you will have “Eden” game boards that cannot be produced by a previous step. 7) Tile solver: a bunch of people have suggested pre solving tiles, and I love this idea - it’s one that I tossed around too late down my path of pixel-by-pixel SAT. You’re trading precompute time and memory to build an enormous library: find every way to back up a 3x3 area and save them, then catalog if a tile is used to back up a particular state, what tiles could be adjacent (this will chop down the long list to a less but still quite long list), then you can build a solution from tiles. Maybe by making tiles from tiles iteratively you could precompute solutions for quite large patterns. This may be an interesting way to cut down run-time complexity pretty massively. I didn’t initially go this way because I felt it would be difficult to keep the simulation small while taking multiple steps backwards, but that could be sorted by your tile selection method/biases (a sat solver would be faster but it’s not easily biasable)

[@tomholroyd7519]

Garden of Eden patterns were proven to exist. So in the worst case it is irreversible. It may be hard to find examples of Gardens of Eden --- oh, it seems you found some!

[@youngbloodbear9662]

Why couldn’t you invert the rules and check the possibilities that meet those rules?

[@yaksher]

Minor correction is that "NP" (which as you say at one point) is "nondeterministic polynomial" which does _not_ mean it is not polynomial. We're "pretty sure" that NP-complete problems cannot be done in polynomial time, but proving it is literally a million dollar problem and it's not _known_ to be impossible to do in polynomial time.

[@yorthundir7343]

It's not really important to the eventual purpose of the video, but I got caught up by the map at 17:30. I assume the edges wrap, which would account for the odd shape of the ring, but a lot of the top points on the ring are unbalanced despite being of equal height to full solutions next to them. I also don't see any space for solutions that are 3/4 one density and 1/4 of the other. In the end it's either just an imperfect example that demonstrates what it needs to just fine and I shouldn't be thinking about it this hard, or I'm missing something glaring, which is equally possible.

[@georhodiumgeo9827]

Can you say what that library was and maybe a link? Python I'm assuming? Great video! I watch everything p vs np related and all of your videos so today was a great watch.

[@Tandanuu]

Bro just made a whole series about entropy and thermodynamics and now he’s surprised that reversing something like Game of Life is hard? :D

[@Windows__2000]

It is kinda unintuitive that a system can be deterministic in only one direction...

[@ckq]

@@Windows__2000not really if there's multiple ways to undo a step but 1 way to go forward. Or just create a measure of entropy

[@GigsTaggart]

​@@Windows__2000a little bit but it's the idea behind cryptographic hashing and RNGs and a lot of CS stuff.

[@hadensnodgrass3472]

​@Windows__2000 Hashing is the fundamental principle of privacy on the internet, computers in general. Hashing is crazy simple in one direction, while becoming an NP Hard problem in reverse. Large prime encryption key methods work in a similarly way. However they encryption is easily reverseable if you have the private prime key. To compute the private key is an NP Hard problem. Gotta love NP problems, that is why it is one of the Millennium Problems.

[@321ooo123]

Actually it's not as simple as that. Entropy can be decreased locally at the expense of an even bigger global increase. So it could be that you'd be able to reorder GoL at the expense of some other increase of entropy. (Not the case with GoL, however).

[@brothertyler]

Surpised you didn't show a solved rubics cube and ask the viewer to try to figure out what unsolved state it began from

[@AlphaPhoenixChannel]

lol I love that

[@DeadJDona]

on step -1 of solving cube you could only rotate slices from single spatial direction, on step -2 from another (or same), etc. this kinda decrease field of possibilities

[@HolmesHobbies]

Perfect analogy!

[@BryanLu0]

​@@DeadJDonabut a Rubix cube solve could've taken 20+ moves

[@Jone952]

@@HolmesHobbies Is it? Every starting state is a valid one for a solved rubics cube

[@satibel]

"we did it not because it was easy, but because we thought it would be easy" (Naive developer discovering that the algorithm they are trying to reverse is not bijective)

Bijective or not doesn't necessarily make much of a difference for how hard it is to compute. Eg mapping between positive integers and their prime factorisation is bijective, but one direction is hard to compute.

[@imsleepy620]

Bijectivity doesn't imply ease of computability in each direction, but lack of bijectivity might imply a lack of ease of computability to find the inverse image, for some general enough class of functions?

[@gabrielfonseca1642]

@@imsleepy620 I don't think that's true either. As a simple example, consider the problem "for a source and a sink node, find the shortest path between them". There may be multiple shortest paths, but it's solved easily. The inverse "given a shortest path, find the source and the sink" is completely trivial, and has only one solution.

[@imsleepy620]

@@gabrielfonseca1642 You're right, revisiting my comment I realize I was definitely wrong.

[@jucom756]

Yeah lol a solution might just not exist, or a 2 step solution might exist from one 1 step solution but not from other 1 step solutions lol

[@procedurecall4219]

Computer scientist here. If you're just using the SAT-solver built-in to Z3 (as opposed to SMT constraints), you should really instead be using a specialized sat solver like cadical or kissat. They're much much much faster. >1 week for one sat solve at the problem scale you're dealing with is almost always unnecessary. The annual sat competition does a good job keeping track of what's currently fastest. If you're actually using SMT constraints in Z3 (like you were previously with integers), you should almost certainly switch to CVC5. It is also much faster than Z3 in almost all cases (save for some theories that you won't use). Also, you almost certainly should not be doing manual a local search for multiple steps like you are now. It should be very straightforward and fairly efficient to encode multiple steps of your constraints at once into SAT (or SMT). Then you don't implement manual backtracking (which I'm assuming is what you're doing currently with your "edens") - that's already what DPLL does (and hence what CDCL emulates). I'm not sure what your constraint formulation looks like, but also see if you can add any "symmetry breaking constraints". It shouldn't be too hard to find good resources on why these are useful and what they look like. Not super important, but also the thing you're calling a "phase space" is what would be called a "reconfiguration graph" in my field, since it's a graph over the space of configurations whose edges correspond to a certain type of "reconfiguration move" (in this case, flipping the colour of a grid point). There are some much cooler reconfiguration graphs. Fun fact the simplex method for linear programming is a greedy reconfiguration graph traversal.

[@AlphaPhoenixChannel]

The most successful algorithm I’ve tried takes a number of steps backwards at once - as many as I can until it hits a computational limit of multiple days. I’d be very interested to know if there’s a solver optimized for inequalities - my best-performing single-step iterative solver was seeking to leave as few live cells as possible.

[@AlphaPhoenixChannel]

I know it’s not kosher, but I colloquially call phase spaces, configuration spaces, and parameter spaces the same thing

[@procedurecall4219]

@@AlphaPhoenixChannel You're much further along than I thought if you have a multi-step implementation, nice! For inequalities, ILP solvers are often recommended, but in my experience they don't perform very well on these sorts of highly combinatorial problems. Z3 has an optimizer built-in that I'm sure you've already found, but it is extremely slow, even on much smaller problems than what you're dealing with. Since actually finding the absolute minimum is actually a very strong constraint (requiring either exhaustion or a lower bound, or some combination of the two), you might get better results by relaxing it to some heuristic bound on the number of living cells - say, at most 10% more living cells than what you started with. Any chance you're planning to publish your code? I'm curious to see if there are low-hanging improvements. Also, if academic publications in overlapping math/cs ever interest you, this is exactly the kind of thing the folks at jcdcggg really like.

[@AlphaPhoenixChannel]

@@procedurecall4219 I had luck with the SMT solver using an inequality to limit the number of live cells and slowly climbing with that limit until I got a solve. It didn’t work well (ground to a halt) for multi-step solves where I tried to limit the number of live cells in the final step, and I couldn’t come up with a way to limit the number of live cells once I went full Boolean (aside from just giving it a small bounding box)

[@AlphaPhoenixChannel]

That 10% more limit is startlingly close to what I was actually able to attain lol

[@Drawliphant]

"Conways Game of Death" completely fair name because it kills the developer

[@sumner1107]

Covid 19 killed the developer (Conway)

[@jasonhildebrand1574]

He survived this round.

[@haph2087]

Agreed.

[@hujackus]

Since I discovered cellular automata 22 years ago, it hasn't left my attention. I finally got my VST to start working after 14 years 😂 kzbin.info/www/bejne/h3a2lWV6q5hkfqc

[@SkoddieAltair]

I’m a software engineer, and I used to work with data that required n-dimensional arrays. At first I was really confused trying to imagine a hypercube of cubes in my brain. As you’ve noted, it’s extremely difficult. One day I was staring across my office at my file cabinet, and I realized that when dealing with arrays using grids & cubes are just an abstraction. There’s no reason to conceptualize arrays in dimensions, it’s much easier to imagine them as containers. Like squares -> grid -> cube -> drawer -> cabinet -> storage room -> building -> etc. It’s not a complex shift in metaphor, but for me it made the notion of distance between cells much easier to understand. I use the same logic when thinking about configuration space. Containers of containers of containers of containers. It’s surprisingly effective!

[@alexpetrov3289]

Same for me, i wondered how to solve a place-time problem and while thinking about higher dimensions, i stumbled upon the realization, that it is just simply a matter of simplifying the complex system and separating each of the dimensions until we get something which is manageable by the human brain to comprehend. Basically shadow projections. And i have it noted somewhere (as this was a passion project more than anything), but transforming each dimension to a lower one takes some amount of calculations and translating between dimensions is a matter of reversing the calculations, and communicating between the created layers of lower dimension objects is a matter of finding the correct path. Somehow i thought about optimal path cost adjustment, but sadly it was quite some time ago and i need to revise my notes.

[@sykes1024]

That works pretty well to keep some of the meanings straight, but it's not as useful if the actual distances or geometry is what's relevant. Thinking of it in terms of containers of containers kind of obscures the fact that [1][0][0][0][0][0][0][0] is actually quite close to [0][0][0][0][0][0][0][1]. From the container perspective, these two would be completely different neighborhoods.

[@michaelcombrink8165]

when i was in highschool i tried making a way to chart infinite dimensions my solution was filmtape, like in old loony tunes where they break the nth wall and the photo reel shows up on the screen i thought why not display time as a photo reel of cubes and why not display cubes unfolded eg front side and top view then we have a line of cubes for time, so why not go perpendicular for alternate timelines and then we have a square of timelines so why not strech the square into another cube and then strech that cube into another line, point, a line is an infinite range of points, a 2d plane is an infinite range of lines, a 3d plane is an infinite range of 2d planes, a 4d plane is an infinite range of 3d planes point, line, square, cube, line, square, cube, line square, cube, ,,,, another way to do is is with axis arrange a series x,y,z axis graphs vertically then copy that series horizontally then copy that in depth then all those vertically again though i enjoyed the cube display more because it showed how the simpler dimensions existed within or contained inside the higher dimensions

[@oafkad]

That false solution thing is also the mechanism behind a lot of "Why didn't evolution lead to X!" conversations. You basically never will go down a hill, even if the evolutionary mountain on the other side is four times as high. Creates these feedback loops where animals keep terrible systems because in order to improve they'd have to "unwind" first.

[@bozodragojevic]

Meteors are the "unwind"

[@CoolAsFreya]

The maths term is "local maxima" which might not be as high as the "global maxima" (largest peak)

[@theapexsurvivor9538]

Yep, it's also what causes convergence, as certain local maxima are really massive in the phase space of selective pressure solutions, and thus regardless of how inefficient they might be, they continuously pull in more species. (Crabs aren't the ultimate body plan for most niches, but they're a Very attractive one due to how much their traits reinforce each other)

[@Appletank8]

my favorite fact is the laryngeal nerve needing to make a detour down to the heart before going to the neck. It'd be nice for the nerve to connect the right way from the start but there's no practical way to disconnect and reconnect elsewhere during embryo development. making it longer is way easier, which resulted in the poor giraffe not able to make proper sounds.

[@VeryLostFisherman]

Yeah the common one I hear is, apart from flagella, why don't we see more wheels in nature for movement? Everything that is not quite a rotating wheel is bad. It requires walking down too much in phase space relative to competition

[@moth.monster]

Another problem which is NP-hard is placing conveyor belts in Factorio. Someone made a modified SAT solver that just makes custom belt balancers for you.

[@DackelDelay]

got a link by chance?👀

[@adrianozambranamarchetti2187]

​@@DackelDelayI concur

[@user-nj1qc7uc9c]

link plz

[@submachinegun5737]

Been playing factorio for a while now and I think I’ve mastered or at least understood most systems but compact belt balancers are just black magic to me, just grab a blueprint online and pray to the omnissiah it keeps working fine

[@evanbarnes9984]

Dude I NEED that

[@8bit_cat72]

During the video I considered this "what if you just checked every possible combination" but turns out that with a 10 by 10 board, if each combination takes one microsecond it'll take 40 quadrillion years to check them all.

[@AsmodeusMictian]

That's the weird thing about problems like this. There's almost always a solution that's intuitive. "Well of COURSE it would work like this!" Then you try it out and it fails almost immediately and you're left scratching your head like "how? how did that possibly fail??" I have to admit, it's that fact that keeps me endlessly fascinated even about math I can barely comprehend :D

[@sykes1024]

In practice, the way a lot of problems with massive search spaces like this are solved is by simply giving up on a perfect solution and using algorithms that are very fast at finding solutions that are "close enough". This is usually what is done in practical applications where you need to solve the travelling salesman problem. You *want* a solution that is the fastest route possible, but a route that is "probably only 1% slower than the fastest possible solution and *might* actually be the fastest solution" is good enough. Because while the laws of NP-hardness can't be broken and magically solved in polynomial time, depending on the problem and how close is close enough, there might be very fast algorithms that can solve the problem close enough. Obviously, in APC's case, finding specific backwards steps that only "almost meet the criterion" aren't good enough. At the end, he wants a solution that follows the rules exactly when played forwards to produce the youtube logo. But what might have worked is to allow for some "good enough" solutions is to simply relax the shape of the play button. There might be other patterns that look like a play button as well, and algorithms that maybe could find one of these other ones quickly. Though, I kind of doubt it given his other criterion that he wanted the ending play button pattern to be stable. I imagine an algorithm that was good at finding sequences that lead to approximate solutions of a pattern at the end would almost always find patterns that only fleetingly look like you want and then decay since most random patterns in the game of life are fleeting rather than stable.

[@bacicinvatteneaca]

Really? 10¹⁰ is that much? Shouldn't it just take at most 10¹⁰ microseconds to test them all? That's 10⁷ milliseconds, 10⁴ seconds, less than 10³ minutes, less than less than 10² hours, less than less than less than 10 days...

[@8bit_cat72]

@@bacicinvatteneaca The amount of combinations is actually 2^100. A 10 by 10 board has 100 cells, each can be either dead or alive, 0 or 1. So each combination can be represented by 100 bits or 2^100. 2^100 = 1,267,650,600,228,229,401,496,703,205,376 while 10^10 is only 10,000,000,000.

[@Axolotine]

Heartbreaking: someone has solved your non trivial problem but used completely different terminology you were unaware of meaning that if you just knew what you didn't know you didn't know you would have saved yourself endless headache

[@AlphaPhoenixChannel]

Care to enlighten?

[@Axolotine]

@@AlphaPhoenixChannel I mean to say, I didn't know about SAT solvers and it could have saved me a lot of time lol

[@Houshalter]

​@@Axolotinethere are people who have spent years writing custom solvers for problems that are easily done by SAT solvers. It is the worst marketed field of computer science.

[@joshuascholar3220]

I get SO frustrated with other people's videos because they DON'T understand the problem they're looking at to the depth you do and they don't explain it. Thank you for making the first video I've seen in a long time that lacks the hand waving of incomprehension.

[@MooImABunny]

I really love how Gerrymandering is relatively much more computationally easier than reversing GoL states. Like, oh, making this cool pattern pop out? insanely hard, computationally intensive. Abusing loopholes in a democratic system leading to political corruption? yeah dude, it's a walk in the park

[@user-nj1qc7uc9c]

the reason it is easier is because we are just looking for a "good" solution; we are okay with reaching false summits with our gradient ascent algorithm with reversing GOL, we are specifically looking for a *perfect* solution so yeah, as it turns out, election rigging is computationally easy! :D

[@NgenDoesGaming]

Relevant XKCD: 1425

[@Dong_Harvey]

Get rid of the "representative" part, nobody can represent a group

[@AsmodeusMictian]

@@Dong_Harvey Well, I'm convinced. No need for any context for your remark or data or that pesky "proof". Just a bold, clear, and very inaccurate statement. I'm SOLD!!!

[@mshonle]

The N always stands for Nondeterministic. The NP-hard problems in NP are those that can be *verified* in polynomial time. It’s an open problem (with a million dollar prize!) to prove or disprove if all the problems verifiable in polynomial time can be decided in polynomial time. - So, polynomials are still very much involved! (Note: the qualifier of “NP-hard in NP” in necessary, because there are undecidable problems that are NP-hard: the Halting problem is famously undecidable, but it’s trivially easy to reduce any NP problem to the halting problem: simply prepend a string representing a Turing machine that solves that NP problem. Likewise, if the N actually stood for “non” then it would include the halting problem as well.)

[@Azrael1123-was-taken]

while that's *true* (and I would assume alphaphoenix knows it is), I read that "Not Polynomial" more as a simplification for the viewers that might be less involved in computer science; as all simplifications do, it leaves out some detail, but since we're not here to solve a millenium problem, we might as well treat NP problems as not solvable in polynomial time

[@jacksonmagas9698]

Its easier to just say NP complete, and only say NP hard if you actually mean to include EXP and beyond.

[@MadocComadrin]

​@@Azrael1123-was-takenThe problem with using "Not" instead of "Nondeterministic" is that you actually make a statement that's kind of false if you use an equivalent definition of NP: the class of algoritms decided by a Nondeterministic Turing Machine in polynomial time. To say it's not polynomial is wrong without being more specific.

[@Arkios64]

I'm incredibly chuffed at the recent trend of not deciding that "this video idea takes way too long to arrive at the final stage to be worth a video" and instead adapting it to "this incredibly simple looking thing took me incredible effort, let me explain to you the surprising reasons why". A lot of my favourite channels have been putting out partial successes or outright failures and creating absolutely wonderful pieces of content.

[@Kargoneth]

It's like trying to reverse a hash.

[@jimburton5592]

What season did Barry Allen finally defeat the Reverse Hash?

[@dcnick3]

Reversing a (cryptographically strong) hash is kinda even worse, because there's no metric of how close you are, the only real algorithm is an exhaustive search of the inputs

[@deltamico]

I searched if simple hashes are threatened by quantum computing and apparently not as much as assymetric keys

[@jimburton5592]

@@deltamico I like adding color codes for an added layer of security. My favorite is hash browns

[@spicybaguette7706]

Imagine using a game-of-life simulation as a hash function. It would perform terribly, but it would be super cool XD

[@pykapuka]

Thanks Brian, I love this video so much! I didnt know something like Z3 existed. This is like telling me "Did you know: if you wiggle your arms like that, you can fly?"

[@jokebird6479]

This has given me a really good understanding of configuration space and p vs. np problems. I’ve always wondered about p vs. np problems but I could never find an explanation I found intuitive. Also, I can’t imagine just how useful configuration space will be to me, being able to think and compute higher dimensions! Thank you for this video, it’s awesome!

[@jonasmaier6631]

24:10 to be completely precise, it is not known if NP-complete problems require non-polynomial time to solve (but it is widely believed to require exponential time and all current SAT solvers are running in exponential time (with some heuristics to hopefully be fast in easy cases)). Just one of those open problems in computer science.

[@columbus8myhw]

Arguably it's _the_ open problem in computer science. It's the most famous one: P=NP.

[@Frank01985]

In addition, although the entire class of SAT problems is NP-complete, that does not mean any one instance of a SAT problem can not be solved in polynomial time. In fact, it's quite easy to come up with subsets of SAT problems that can be solved in polynomial time (e.g. those that can be separated into smaller, fixed-size SAT problems because variables do not overlap). So it is very well possible that the problem of finding the previous state in game of life, expressed as a SAT problem, could be solved in polynomial time, even if it was proven that the entire class of SAT problems could not be solved in polynomial time.

[@jonasmaier6631]

@@Frank01985 reversing game of life is NP-hard. You can do Turing machines in game of life, hence you can also do boolean circuits in game of life, and if you try to reverse those you're essentially solving SAT.

[@Frank01985]

@@jonasmaier6631 That makes sense when considering reversing more than one step. I wonder if this still holds for reversing just one step into one feasible solution (instead of enumerating all solutions). A boolean circuit will need more steps to compute a more complex circuit. I could see it being the case that reversing one step can be done in polynomial time, but considering the combinatorial explosion of all possibilities that need to be searched for multiple reverse steps, that that is not feasible in polynomial time.

[@gabrielfonseca1642]

@@Frank01985 Yeah he reduced game of life into SAT, which doesn't say anything about game of life's complexity. But I don't think the point of the video was to show reversing game of life is NP-hard. Other people pointed him to the SAT solver already knowing the problem was NP-hard. I think solving even one time step is NP-hard. If it was solvable in polynomial time, I don't see why you couldn't just iteratively solve it to get the desired starting configuration "n time steps ago" (I could be wrong though).

[@4ntig3n]

I love this video. I love how it tickles parts of my brain, makes me think of problems differently. Right now my head still hurts, but there is also that feeling of wow - this is a new path.

[@manuelpena3988]

I once heard a very clever computer scientist say: We programmers do no choose what we work on because it is easy. We choose it because we thought it would be easy!

[@jeffpkamp]

Videos like this can destroy somebody's entire year! I'm glad you were able to set the project down every now and then.

[@harold2718]

Have you looked at zero-suppressed decision diagrams also, they "break down" (by running out of memory) more often than SAT solvers but when they work they enable you to ask questions about the entire space of solutions (instead of just getting one of them, as SAT would, making you generate them one-by-one with extra constraints). Such as you can ask how many solutions there are, or even a list of pairs of how many solutions there are for each number of "live" cells, or find the solutions with the most or least life cells.

[@Mikee512]

A ZDD is an efficient* way to encode solutions to a boolean function, but you still need to calculate the solutions, which I think is a significant portion of the difficulty here. *ZDDs are efficient in that they encode the solutions in the smallest possible datastructure which, because boolean logic, also turns out to be maximally efficient to search/query (assuming you can figure out how to write an efficient algorithm to query it for what you want to know, which is part of what SAT helps with in the first place.) However, just because it's maximally efficient doesn't mean a complete solution set (or even a sufficiently-interesting subset of solutions) will fit within storage/RAM constraints, or be traversable in a reasonable amount of time. The solutions the SAT solver finds could be used to build up a ZDD, perhaps incrementally, for efficient searching later? There's a software package called CUDD that helps working with ZDDs. Anyway, it's interesting to think about how it might be useful in this context. A few caveats may limit its usefulness: * Because building a ZDD presupposes having solutions to encode into it, if finding the raw solutions is the primary difficulty, then ZDD's usefulness may be limited * And while a ZDD is a highly efficient datastructure, whether you can express the precise query you want to ask in a form that runs efficiently, depends on whether you can reuse existing efficient queries or figure out how to craft your own, which can be non-trivial.

[@harold2718]

@@Mikee512 You wouldn't create the ZDD by finding all the solutions and then converting them to a ZDD though (you could, but it's not efficient, as you identified), you'd build it by melding together ZDDs representing individual constraints

[@Schlimbinger]

This reminds me of something. A while ago a buddy and me made something similar using langtons ant. We used multiple ants at different starting positions to “encrypt” a message. The world the ants reside in basically was a 2d-grid representation of the input message bytes. They then would do their thing for many iterations. Just a fun project, nothing serious. But it was nice to see your message emerge from “random” noise :D Never thought about how one could crack it but it would not surprise me if it’s relatively easy lol

[@MrAppleGuySnake]

That's amazing, how did you implement it?

[@Schlimbinger]

@@MrAppleGuySnake We used many ants (the amount depended on the grid size) that were randomly placed on the initial grid. The ants moved according to their rules and changed the grid for a fixed number of iterations. After that the resulting grid basically represented the encrypted message. Every "Pixel" of it can be seen as bit. Those bits were turned into a byte array. We also returned the number of iterations, the grid size and the ant locations+headings as an base64 string. This acted as the key for decryption along the "encrypted" bytes. The decryption was the same procedure but in reverse. Reconstruct the state of the simulation from the base64 string and move the ants the same number of times, just in reverse. If I find the time (and the code :P) I will share it with you here :)

[@carnac333]

Awesome video and explanation!! This reminds me of my research area of inverse problems, where one aims to reconstruct the object of interest from indirect measurements. As an example, in Computed Tomography (CT), we reconstruct the image of the imaged target from x-rays projected through the target. The information of the inner structures is encoded into the measured x-rays, which have been attenuated proportionally to the attenuation different tissues (for example very high in bones and lower in soft tissues). Commonly, the inverse problem is formulated using a model for the x-ray attenuation, known as the forward model and the sough after image is obtained by iteratively minimising the difference between the measured data and the predicted data produced by the forward model applied to the estimated image. Often, however, the problems are ill-posed, meaning that the solution might be non-unique, have many local maximum/minima, or noise can have a detrimental effect on the solution. In these cases we often employ regularisation, which imposes assumptions on the solution (such as smoothing) and makes the problem less ill-posed and more feasible to solve. Although this problem is completely different to ones I'm accustomed to, there are many parallels. The forward model is the algorithm that runs the game of life, the indirect measurements (measured x-rays in CT) are the starting point, the final sough after image (CT image) is the final image you are after for and problems with optimisation (local minima/maximima) are common. Very cool to video!

[@JTCF]

33:33 "Eden found" did the computer just die and ascend to heaven?..

[@NorthOfEarth]

At 10:00 I noticed something interesting. Traversing diagonally across a face always flips the same two pixels. Look a the front face. The top two pixels change along each diagonal, but the bottom one is never affected. Along the top face, diagonals flip the left and bottom pixels, but never the right one. Similarly, traversing the 3D diagonal flips all 3 pixels. A 4D diagonal four flip 4 pixels, etc. This means a path length of sqrt(n) would always flip n pixels, making plotting a path much easier to calculate. You could imagine a large image with huge chunks of pixels being the wrong color. Instead of navigating through configuration space in cardinal directions only, you could take a shortcut by pre-calculating and caching the diagonal that corresponds to flipping that entire chunk. Maybe divide the whole pixel array into smaller square chunks for faster processing, etc, etc.

[@lukatambourgi9372]

4:00 its impossible to compute THE previous state. Easy example: an empty board. Was the previous state an empty board too? 1 cell? 2 cells aligned but spaced by 2 empty ones? Or the space between was 3? 4? 99999? Graams number? Tree(3)?????? We cant know

[@berserkforce1809]

Good s example

[@digantamukhopadhyaydex]

also afaik z3 doesn't have any progress bar, did u find that at all anxiety inducing? like if you had stopped the solve 1.9wk after start, maybe you would have missed a solution that you could have found with just one more day of solving

[@AlphaPhoenixChannel]

I don't even remember what its solving right now, but there's been one going for like the past month that I haven't wanted to shut down. it's got to be close... right??

[@ignaloidas]

It's the nature of the fact that the solving involves random guessing - you can't know how close to a solution are you. Some pure SAT solvers like Kissat can give you numbers on how many variables they have left, which essentially shows you the search space that is still left, but that still isn't that useful, because often that remaining search space could take until the heat death of the universe to complete.

[@ivanovtv9817]

99% of z3 users terminate the program right before they find a solution

[@Momi_V]

​@@ivanovtv9817 *right before being a relative term in relation to the end of time itself

[@Joonazan]

It has been shown that restarting after some (steadily increasing) time is optimal for certain SAT-solving algorithms. Probably Z3 already does this, though.

[@FAT9L]

FINALLY, an answer to the burning question I've been asking myself for decades: whether it's more difficult to reverse Conway's Game of Life or to gerrymander the state of North Carolina

[@ohadcohen9813]

5 minutes into the video and I was screaming at the screen USE SAT SOLVERS! Glad you went there eventually, and I hope you had a wonderful eureaka moment :)

[@jacksonmagas9698]

I saw the thumbnail, thought about it for about a minute, and then said "this is just SAT isn't it" Boolean variables (cells) with constraints, and you want to see if there is a satisfying assignment to those variables.

[@acf2802]

I bet reddit still thinks it can't be done after watching this video.

[@guy9360]

"He didn't ACTUALLY do it, he simply ..."

[@OrangeC7]

Oh yeah! My favorite Blokus tile is the pentomino that's, like, a 2x2 square with another square attached to it. I don't really think it's the *coolest* one but, it's pretty unique all things considered so it ends up being my favorite

[@AlphaPhoenixChannel]

i always thought that was one kind of a weird lump shape - granted when you can use it perfectly to flatten a rough wall, its extremely satisfying

[@fuuryuuSKK]

so the P-pentomino. Also, the "r" mentioned earlier in the video is actually more commonly called the F-pentomino

[@TypicWhisper]

@fuuryuuSKK It's almost always referred to as an R-pentomino in the context of Conway's Game of life, as Conway had his own names for the pentominos.

[@GDTerietto]

i gotta go with the C-pentomino

[@fuuryuuSKK]

@@GDTerietto Pretty sure that one's commonly called the U?

[@steubens7]

did you hear about Golly during this investigation? it runs finite automata extremely quickly because of a method called hashlife. it memoizes computed blocks to advance larger and larger patterns more quickly than evaluating the rules. you can use it to look backwards by looking forwards, unless there's an *incredibly* improbable situation that can never happen under a certain sized starting condition, it will find it

[@SimonClarkstone]

I was wondering if you could do something like Hashlife too. It would start with all the ways to reverse a 2*2 configuration to get some 4*4 configurations, then try following back only the parts in the end image and matching the overlaps together to build up the ways to run the needed 4*4 configurations backwards 2 steps to get 8*8 configurations, then match up the edges of those (by the recursive hash) etc. I expect the hash tables would soon get impractically huge though.

[@Avidiax]

For much of the video, I was wondering why there would not be a way to precompute all (k+1)*(k+1) automata as a way to stitch together a k*k solution. If k^2^2 ends up being too large for memory, then a variation of rainbow tables could be used, albeit with the problem that many states evolve to "everything dead", and for large k there are many states that are translations of each other that should ideally be coalesced.

[@momom6197]

It would indeed help a lot for reversing large configurations when you have some canonical preceding configuration (e.g. there are a lot of gliders in the figure and you make their ancestor another glider), but it wouldn't help with the hard part of the problem which is finding some ancestor in the first place.

[@heh2393]

27:48 in practice we encode such "sum" constraints for SAT solving in a different way that's much more succint; see Tseitin's encoding

[@AlphaPhoenixChannel]

Oooooh

[@AlphaPhoenixChannel]

I tried to find something like this and didn’t know what to google! Thanks

[@AMurderOfLobs]

3:50 It's kind of like how multiplying two large numbers is easy, but determining the factors of a large number is hard (so hard all modern cryptography and indeed the security of the internet depends on it).

[@Krunked]

that is extremely abstract. but i love it. tickles my brain. i dont get this sorta thing at my work (site reliability engineer), but this reminds me of cool science classes i loved in higher ed. i love these vids thank you for making them :)

[@hhhsp951]

you are one of my heroes and if you successfully guess why I'll work for a year as your personal legislator.

[@jsbarretto]

I've found it's very common for Redditors to over-generalise their knowledge. They might have read "solving P for all configurations of X is impossible in general" and will translate that, in their mind, to "solving P for any configuration of X is impossible". This video is a great example of the fact that 99% of the time you don't need to solve the general problem to find a solution that satisfies a more constrained subset of the problem!

[@czer096]

Yeah it's reddit Bunch of idiot with slightly more knowledge

[@Rudxain]

I guess that's known as "over-fitting"

[@Ergosphere2357]

You managed to find a way to undo steps in Conway's Game of Life!? Hats off to you!

[@I.____.....__...__]

3:47 As Brian found out, that's a specious question. The fact that the GoL has stable loops in the finite-state-machine, means that there's no deterministic way to find a unique pattern that would result in anything in particular. For example, the standard solid 2×2 block configuration could arise as the next step from a very large number of permutations of states from even just the surround few cells, or… another 2×2 block. … 33:12 👍 This video is speeding into NP-completeness territory. … 23:30 👍 34:19 Yeah, that makes sense, because the target pattern will be made from a LARGER pattern, which itself will be made from a larger pattern, and so on. You might get lucky and have a target pattern (or intermediate pattern) that can be made with gliders and spinners and such which can reduce the size of then parent pattern, but most patterns will usually be made from physically-larger non-repetetive patterns.

[@SamChaneyProductions]

You make some of the best content on the platform. Incredibly informative without being dry

[@bennettpalmer1741]

It's funny, because my first instinct when I saw this was "Oh, this is basically minesweeper, that's an NP complete problem we are pretty good at solving, you should just convert it to that to solve it" and after messing around with configuration space for a bit, making me worried I was doing it wrong, you eventually decided "this is basically the SAT problem, I'll just convert it to that to solve it". I basically had the solution right off the bat, but we picked different NP-complete problems to use. I wonder if one is better/more efficient?

[@BetaDude40]

That's the thing about NP-Completeness, they're all basically the same problem just phrased a little differently. If you could solve one in polynomial time, you could apply the same algorithms to all of the problems in NP-Complete.

[@Houshalter]

There has probably been a lot more work put into SAT solvers. They have competitions and investment from industries that use it. Also most computer scientists are familiar with boolean logic, and can probably figure out how to encode their problem into it. I wouldn't even know where to begin encoding something into minesweeper.

[@Wackylemon64]

I love your explanations and visualizations! Your passion is clear! I've been trying to improve my intuition of latent/configuration spaces, and explanations like this are always welcome!

[@flexico64]

As much as I love math(s), the tables problem makes me want to say, "Shut up and eat."

[@SenorSiesta]

Seriously underrated KZbin channel. Most this stuff is way above my intelligence but can’t stop watching these videos super interesting stuff!

[@bretonkyle]

You know you've watched too much This Old Tony when the music at 7:09 reminds you of TIG welding and drilling holes

[@Sidewinder0010]

13:00 thank you so much! I have watched countless videos of people explaining higher dimensional spaces over the years and this finally clicked for me!

[@top1cpvper]

Putting Alice and Bob outside of a cryptography problem should be considered a war crime

[@AlphaPhoenixChannel]

😁

[@dwightk.schrute8696]

You sound like Mallory!

[@evannibbe9375]

Using exile as punishment is now a crime under international law (similar to stripping Alice and Bob of their citizenship to Cryptography land).

[@Dong_Harvey]

They know what they did. Or maybe did not.

[@OtterSwims]

incredible work on this video, you have made a major, meaningful contribution to educating the world about this!

[@tonydai782]

26:06 Hexagons *are* the Bestagons after all.

[@timothynoll4886]

Had to pause the video here and make sure someone acknowledged that hexagons are, in fact, the bestagons. Hehehe 😁

[@BoogsMcNoogs]

I have no memory how I stumbled on your channel but I am very, very glad I did. Keep these coming, they make my brain satisfied.

[@typeswitch]

Oh when I started the video I thought "I hope he's using a SAT solver" and I wasn't disappointed hehe :-) 24:35 NP-hard doesn't mean "not polynomial time" and NP-complete doesn't mean "it can be solved in exponential time". I know this isn't a CS channel but I wish you were a little more precise at explaining these concepts the first time for people who might not already be familiar with them. The visualisation of (CDCL) SAT solvers as crossing out whole swathes of solution space where only suboptimal solutions exist, is really good! Thanks for this insight.

[@AlphaPhoenixChannel]

I know those aren't the rigorous definitions, but they are true statements. I went back and forth a LOT about that segment trying to say what needed to be said relevant to this video (and not too much), but not be incorrect. Edit: The verbiage I used to describe NP complete in the video was “at worst exponential time”, which is a very precise way to phrase it. Claiming that NP is “not polynomial time” in the graphic and saying “no known algorithm to solve in polynomial time” is also I think a very precise way to phrase it. The graphic annotation is practical and the part I said out loud was exact

[@typeswitch]

@@AlphaPhoenixChannel Well, they're not entirely true, no. NP-hard doesn't imply "not polynomial time", it only implies "we don't know a polynomial time algorithm to solve this (and probably never will)". NP-complete does imply "can be solved in exponential time" but so does NP. So does P. etc. It just doesn't feel like a good explanation for why SAT in particular can be used to solve this problem. I think a better explanation would talk about how NP problems have easy to verify solutions, and how this problem has easy to verify solutions (just run the solution forward one step & check that it matches the desired output), and then link that to a brief discussion of NP-complete & SAT solvers (which you kinda already have in the video).

[@ruroruro]

​@@typeswitchmeh, I think that for all intents and purposes NP-hard does kind of imply "not polynomial time". Sure, it doesn't technically imply "we can prove that it's not polynomial time", but "there is no polynomial time algorithm" and "there is no known polynomial time algorithm and it's almost certain that there never will be" are basically equivalent in colloquial use (and I'd argue they are definitely equivalent in the Bayesian sense).

[@theqwert3305]

I saw a *really* cool video recently that rephrased NP vs P as "Can you reverse every polynomial algorithm in polynomial time" The moment I saw the title I went "of course running it backwards is hard, it's NP!"

[@AlphaPhoenixChannel]

@@typeswitch The verbiage I used to describe NP complete in the video was “at worst exponential time”, which is a very precise way to phrase it. Claiming that NP is “not polynomial time” in the graphic and saying “no known algorithm to solve in polynomial time” is also I think a very precise way to phrase it. The graphic annotation is practical and the part I said out loud was precise

[@AlmightyJu2]

As always this is such a good balance between complex, simplified but not too much that all the nuance of how it's complex is lost. Can't wait for the follow up!

[@andytroo]

the game of life is turing complete - assuming you have enough grid space ... does that mean solving this is a limited space halting problem? also, solution to sat: "I can't get no satisfaction 'cause I try and i try and i try" - Description of brute force SAT solving strategies, [Jagger, Richards, et al.; published in "Out of Our Hands, 1965, available online]

[@AlphaPhoenixChannel]

What a great application of lyrics 😂

[@typeswitch]

> the game of life is Turing complete This only matters if you're running the game of life forwards for an indefinite number of steps (& an unbounded grid space). Trying to reverse a finite game of life configuration by a single step is in NP, so it can be solved using a SAT solver, as practically demonstrated in this video.

[@jeffreyblack666]

This is going backwards, not forwards. Comparing it to the halting problem, this is more like looking at the "end state" of the halting problem, in this case a program which never halts, and asking what input gets there.

[@gamekiller0123]

It's not the halting problem. It's related to the existence of one-way functions, but the "reverse game of life" problem might be easy even if one way functions exist. The reason is that reductions rely on encoding Turing machines into the game of life, but you can reverse into states that aren't encoded Turing machines, which then won't give you the inverse of the one-way function.

[@talis1063]

Just did a university homework on local search yesterday. The algorithm that selects the best next step based on a heuristic from a neighborhood of nodes is called the hill climbing algorithm. Even if finding the optimal solution is NP-complete, finding a solution might not be with a metaheuristic algorithm like hill climbing with random restarts. But of course there is no guarantee that a solution is found in a reasonable time, especially if the solution space is very sparse (which seems to be the case here). Not trying to say that anything is wrong in the video, just find it cool that this video popped in my feed with perfect timing and wanted to share.

[@JochemKuijpers]

The main lesson from this video seems to be that you should use the right tool for the job 😄 SAT problems are "too discrete" for a gradient descent algorithm. Arbitrary changes don't result in predictable increases in the result space as there's no real continuous output of a SAT-solver that can tell you how close you are to a solution. The number of requirements met is not a useful metric here, a single requirement may prevent you from solving a problem even if you hit all other requirements. So any notion of 'derivative' or 'gradient' doesn't really make sense for these types of problems. A couple times you referred to the configuration space as 'continuous', but it really isn't continuous at all. Even in the city example you're dealing with discrete cells and boolean assignments. The parameters you used to divide the city may have been continuous but the output is discrete, which should've been the first hint that gradient descent may not have been the best tool for the job. The parameter space also excluded many valid solutions, such as a checkerboard pattern, that would've evenly divided the city. Unless you're certain that your simplifications in parameter space don't exclude the valid solution you're looking for, that's almost always a bad idea. (though, I understand that was a simplified example to make a point 🙂).

[@MrTomyCJ]

I really wanted to see someone try a neural network approach to this. I feel like "deep intuition" may help traverse the messy configuration space.

[@cannot-handle-handles]

True, it's not continuous, but it is at least Lipschitz. The checkerboard pattern isn't simply connected, however. Among the simply connected solutions, I would have liked to see those containing either 1 or 3 city quadrants.

[@LightProgRock]

Amazing video ! I've been playing with the game of life a lot, to generate chords used in my music and now I know that I can decide that I want the last chord to be one specific chord, which is really useful !! Now I don't know if I will becaise it seems to be really hard, but… maybe one day 😅

[@johnreiland9180]

Around the 7:30 mark, when you are explaining Configuration Space, the music is quite loud, to the degree that I think it becomes an obstacle to cognition. Love your videos, not hating on you or them, just wanted to mention this small spot that I think can be improved.

[@y00t00b3r]

grr, hate that

[@StuartWoodwardJP]

Yep. music behind an explanation is really distracting. I didn’t enjoy that segment.

[@dracuul78]

This is a captivating topic and an amazing presentation, thanks for putting in so much effort!

[@H_fromDiscord_real]

0:52 this is called the f-pentomino, and it's mirror image is called the e-pentomino

[@yodxxx1]

Thanks dude, you are helping me a lot with this video, thanks to you i now have found a few new paths to solve a logic problem i had for some years now

[@zncon]

It took a while of watching for this to dawn on me, but the game of life is essentially a one-way hashing function. For the sake of all the worlds digital security I'm glad you didn't manage to conjure up a universal solution.

[@andreyzyablikov9891]

Спасибо за это увлекательное путешествие в мир NP-задач, теперь я стал понимать, в чём проблема NP. И ваше стремление найти решение в этой "тёмной комнате", где даже не известно, есть ли в ней "кошка", меня восхищает! Удачи и сил продолжать подобные поиски и спасибо за видео!

[@duncanbyrne1134]

To me this sounds like a perfect inverse problem. Pretty much how do we go from a current state and work our way backwards to find the initial state, given that the initial state has pretty much infinite possibilities and there are infinite solutions. Inverse problems are pretty heavily studied at least in geophysics and hence there are some solid algorithms for them. That might be another approach to solve this problem which could make it much faster.

[@Trainwreck1123]

I love your videos! Your channel is near the top of my list for new videos I get excited about :)

[@stanleydodds9]

Nobody knows that NP complete problems cannot be solved in polynomial time. It is generally considered unlikely that they could be, but we do not know any reason that NP complete problems cannot be solved in polynomial time; that is, NP may be no larger than P, which of course would make it equal to P (trivially all P problems are also non-deterministic P). All that "NP complete" or "NP hard" means is that it is a problem that can be solved non-deterministically in polynomial time (that is, it is in NP), and also it is maximally hard. A maximally hard NP problem is one where a solution to this problem can be reduced to a solution to any NP problem (with at most polynomial slow-down). The typical example of such a problem is, of course, SAT. It's no coincidence that we use SAT solvers to solve all NP problems - SAT being NP hard exactly means that a SAT solver can solve all NP problems without significant slow-down. We also know many other NP complete problems, i.e. many problems that can be reduced to all NP problems, including each other. It's just that SAT is quite probably the "simpl. Secondly (but similarly), EXP (algorithms that run in exponential time) is weakly larger than NP, and it is suspected to be strictly larger than NP. Or put another way, NP is closely related to polynomial time (it's about a more general idea of polynomial time than P); it is not really about exponential time per se, although it is trivial that NP problems can be solved in exponential time by the naive brute force algorithm of checking all possible solutions. But note that also P problems, or indeed any easy problems, can be solved in exponential time. It's trivial in the same way that solving NP problems in exponential time is trivial. That doesn't necessarily mean exponential time is the fastest we can do for NP problems, and it doesn't mean that all exponential time problems can be verified / solved non-deterministically in polynomial time (they probably can't all be).

[@fakesilver746]

this was so cool! I took a course in uni that included sat solvers and i always thought they were really cool but this is the first time I see someone using one in the wild. I didn't really understand how you encoded the pixels into numbers, with rules and everything, but i really liked the video! subscribed :)

[@justindie7543]

Gotta love redditors. Never ask reddit for advice with anything if you want to be optimistic about it in any way.

[@OvrcstYT]

Holy moley, this video was fascinating. Can't wait for the second part!

[@rieduciumaratonas]

I worked on a similar problem, difference being that my solution did not have to be exact, just similar. I used genetic programing, but didn't get anything. Maybe I will revisit it with new ideas.

[@andersama2215]

When you opened with this video and started to explain the project, my initial thought was, oh this is like backtracking algorithms to solve sudoku, and then immediately was reminded of SAT solvers like Z3.

[@Veptis]

So, Injective functions... now the fun part... This can be applied to Jpeg Compression as well. Which is a esoteric paper I want to write one day. Some configurations can't be reached, so they only ever are an initial setup. meaning there is some order to this too.

[@AlphaPhoenixChannel]

hahahaha i didn't know there were jpeg edens

[@Veptis]

​​@@AlphaPhoenixChannel Think about it this way: there are fewer possible compressed images than uncompressed sources. So you eventually have to map two slightly different images to the same compressed one. It's sorta a form of noise reduction. Jepg isn't deterministic, since you can chose the quantization tables arbitrarily (which means some jpegs look better than others, even if they are the same resulting file size/entropy). but you should be able to do the reverse and find a whole set of images that compress to the same result. Now one fun idea would be to figure out all of these (I assume mostly noise). But the more interesting idea would be finding a more appropriate comrpessed image you want.... And then finding it's input. You might think that all compressed versions are the best possible ones but that's not quite true. Things like text compressed with jepg look horrible. But by adding extract lines, you can improve how the compressed result looks by targeting a specific compression table. Maybe sorta think of it like the extreme patterns that were needed in near UV lithography? Or people putting thin cavities in their 3D models so the slicer adds internal walls for additional support. Since jepg is meant to be visually lossless, that means the mapping won't be uniform.

[@Respectable_Username]

I think I've been taught 3SAT in at least 3 different courses and had to create a solver as an assignment for at least one of them (which I successfully did). Do I still forget how it works every single time? Yes, yes I do.

[@BrianJorgensenAbides]

YOU underestimated this? My lecturing fingers were all ready to go for nothing. For everyone else, it's the exact thesis of Stephen Wolfram's entire life that you can't do this (I'm a fan, but poor guy, he'd never heard of church-turing, or long division, or the weather ;)

[@backwashjoe7864]

I think I've been nerd sniped on whether or not Brian's comment has a dangling parenthesis.

[@mdderrek9280]

I can't believe how good this content is, you rock man!!!! I also cannot stress more about your series about electricity, the most intuitive on the planet, please do more on that topic !!!

[@maxmustermann3938]

Remember learning about this back at University, we also went through some proofs for whether a problem is NP-complete and had to do some on our own as assignments. To proof something is NP-complete involves two steps: 1) Proof that it is NP-hard 2) Proof that it is in NP In order to prove that a problem is in NP, all you need to do is show that a certificate (of polynomial length) exists that can be verified in polynomial time. Usually, the "certificate" is just a possible answer, for example a specific configuration of true/false for each variable, which can obviously be checked whether it satisfies the given conditions in polynomial time. That places the problem in NP, because we could just try all possible configurations (non-polynomially many) and verify them each in polynomial time. For NP-hardness, you need to show that every problem in NP can be reduced to your problem in polynomial time. This sounds complicated, but these reductions are transitive, i.e. you just show it for one known problem such as SAT and you're done (i.e. the other way around compared to what you did in the video). Is your problem NP-complete? Probably, but we're missing one step to actually prove it, since you reduced your problem to SAT, not the other way around. Clearly, the problem is in NP (a solution is of polynomial length and can be verified in polynomial time with forward conway). But we don't yet know if we can i.e. express SAT itself in terms of conway. Notable, one of the big open questions is whether P = NP or P != NP (most people believe the latter). If P = NP, then it also follows that every problem in NP is NP-complete, so in that world only one part of the proof is still necessary. However, if P != NP, then there are also intermediate problems that are in NP, but not in P and not NP-complete. Theoretically, your problem could be one of those, but that seems unlikely since then we would have a proof for P != NP. The other possibility would be that your problem is actually just in P, but I think we can safely say that this problem is not that easy. So I am 99.9% confident that it is NP-complete.

[@AlphaPhoenixChannel]

I think I left a paper in the description showing completeness

[@powndy24]

2^36 *1ms /16 cores =2 months. Just saying

[@ivanjermakov]

Best case, don't forget parallelization overhead.

[@AlphaPhoenixChannel]

And the fact we’ve got a LOT more than 36 pixels to consider

[@GerinoMorn]

I know that it ain't gonna help for like doing many steps in parallel, but in general it looks like it could be GPU accelerated... Is this something the Z3 already leverages? Or at least maybe SIMD...

[@AlphaPhoenixChannel]

@@GerinoMorn if you're literally just trying all the solutions, that's parallelization with zero loss. they can each work on a subset. the problem is that you double the number of cores you need each time you add a pixel to the solution space

[@jmacd8817]

​@AlphaPhoenixChannel but the 16,000 CUDA cores in a RTX 4090 can't hurt. I'm not sure if the ~2.2 Ghz would slow you down too much. With the likely pending of the 5090 and friends coming at some point in the not too distant future, more compute is coming.

[@SpontaneousProcess]

Well, power to you! Discovering that your question is equivalent to SAT was already further than I would have gotten. When someone asks me “can you go backwards in the algorithm”, my usual answer is “no” without even thinking about it.

[@Petch85]

Loved the video. I love optimization so I guess that is no surprise. But I think you failed in explaining (the first step of) why the rules in conway's game of life are so hard to run backwards. It seems like if you have a live pixel you could calculate one step back for the 8 pixels around it. And even if you get 2 or 3 possible configurations that could have birthed that pixel, you could just make a "tree" and explore all solutions, that might end up with milions of configurations to be calculated, depending on the number of steps back. But at least all the configurations you are trying will return back to your taget solution. Basically what I am trying to say is that you "fail" to show the views what you explain from 5:51 to 6:23. Not saying that I could do any better 😂. I know this to be true, but honestly I do not "understand" in detail why this is true. And even if I did I don't think it is possible to explain in a youtube comment without being able to show simple examples. I know it would have made the video even longer, but as the video is now the viewer just have to except this as being true and I think that is a little disappointing taking into account how well you explain the solution space over the next 15 minutes. To be fair I don't remember ever seeing a satisfying explanation, I only have a "feel" for it by trying the problem myself. (I tried finding stating solutions that would just keep going, and quickly realized that it was a much harder problem than I could have ever imagined and have not touched the game since. Burnt child dreads the fire 😂)

[@nnomis9349]

11:11 omg this makes me so happy because i made a really simular model of the hypercube in school when i was 9 years old or something

[@seshrut]

Bestagonal, i immidiately paused. 26:05

[@weasel.3683]

haha, nice! We all share a common space in the Internet ✨ Even with high entropy!

[@scttstnfld]

Same, came here to see if anyone else heard it.

[@sushantmanandhar1387]

25:19 absolutely relatable taskbar btw

[@TimothyWhiteheadzm]

The fun bit is reality is almost the opposite, ie it is much easier to 'predict' the past than the future. There are multiple possible pasts, but not many, whereas the number of possible futures is near infinite even on very short time scales. This is why we remember the past but not the future. So a life form in Conways game of life would actually 'live' in the opposite time direction from us and 'remember' what we see as its future.

[@drdca8263]

Eh? I don’t think that’s correct… Maybe you are referring to non-determinism? At the least, I’m fairly sure that entities in GoL can’t “remember the future”, because there is a communication speed limit in GoL , limiting how quickly one thing can influence another thing. You can’t respond ahead of time to a glider that would hit you in 100000 steps because the information that it is headed towards you hasn’t reached you yet. To remember something, one must be able to do something differently because of that remembering. As for the non-determinism, I think that like, it probably balances out equally as far as how undetermined the past and future are? Or… Hm. If you have some prior distribution over the state at time 0 ( i.e. P(S_0)) , and have a conditional probability distribution of P(S_t | S_{t-1} ) for each t… hm, I guess we could describe the amount of uncertainty as the entropy of the distribution? So, I guess the question is about how H(S_t | S_{t-1} , S_0) relates to H(S_{t-1} | S_t , S_0 ) ? Err.. what exactly was the question I’m trying to answer???

[@TimothyWhiteheadzm]

@@drdca8263 I could be thinking about it wrong, but in GoL, the future is absolutely determined. It can be predicted with 100% accuracy. Whereas the past is not. There are many possible past states that could have lead to the current one. In real life it is past determinism (the ability to accurately predict what states lead to the current one) that allows us to remember. But on further thought I can't actually think of a mechanism for 'recording the future' in GoL so maybe I am wrong. Maybe past determinism allows for memory but isn't the only requirement.

[@TimothyWhiteheadzm]

I am fairly sure though that a highly complex entity in GoL could calculate what its future would be, but could not possibly calculate what its past was, although keeping a 'memory' of the past in a finite region might actually be a possibility. Although on small scales it is really hard to predict the prior states, on large scales it might actually be much easier for specific configurations.

[@drdca8263]

@@TimothyWhiteheadzm The future states in GoL are completely determined by the current entire state while the past states aren’t, yes, but a finite sized being in GoL can’t know the entire state of the GoL world. In reality, there is the idea that time evolves under unitary time evolution, in which case both the past and future are determined by the state at any one moment… except possibly for non-determinism in measurements. There is disagreement about how to interpret measurements. (“Is it fundamentally non-deterministic, or is the non-determinism just a subjective thing?”) But, the projections involved… I think they might produce the same kind of uncertainty about the past as they create about the future? Like, if something is in state (|0>+|1>)/sqrt(2) and it is measured in the basis |0>,|1> , there’s a 50% chance of it ending up being in state |0> and a 50% chance of |1> , … but, suppose from the current state you know that it was just measured whether something was in state |0> or state |1> , and the result was |1>, even suppose you know that there was a 50:50 chance there. Well, from that, you can’t tell if the state before the measurement was state (|0>+|1>)/sqrt(2) or state (|0>-|1>)/sqrt(2) (or state (|0>+i |1>)/sqrt(2) or for that matter). With unitary time evolution, “information is conserved”, I suspect that the non-determinism of measurement has to essentially “erase” the same amount of information as it “creates”.

[@drdca8263]

@@TimothyWhiteheadzm Huh, your third comment didn’t show up for me until now. KZbin is weird. If the GoL world is infinite (or merely much bigger than the entity living in it) and the entity’s internal state can be influenced from the outside, then it cannot know its future internal states, because it cannot know what will influence it in the future. Different things far away which it doesn’t know about would influence it in different ways, resulting in different futures (even though only one of the possibilities for the far-away part of the current state is actually true, and so what will happen is determined.)

[@ricardasist]

This is super cool, man you make some really next level content😊

[@magie3490]

Am I mistacking or cant you solve this problem with a wave function collaps algorythem

[@Majromax]

Wavefunction collapse algorithms are essentially a greedy algorithm with backtracking. Given the same SAT problem, take the variable with the fewest still-admissible states, pick one, and repeat from there. When you have potentially many valid solutions and just need to find one (such as when you're doing an aesthetic tiling), then this works out pretty well. The typical example is tiling a game board, where your new cell to fit might have water on one side, a forest on another, and you have several options to choose from. However, Conway's game of unlife does not have that property; it's very constrained since a cell can be only alive or dead. A cell will either be forced by its neighbours (it _must_ be alive or dead, with only one option), or it has two still-unresolved outcomes. There's no obvious way to choose which cell is next-best to consider, so the greedy approach of wavefunction collapse doesn't help very much.

[@magie3490]

@@Majromax yes fair. But what if you take the 3 by 3 grid araound a cell as a possible cell state? I think this could work but i dont have the courage to try out.

[@Majromax]

@@magie3490 Your problem then is that large grids would be overlapping, so you're not solving independent constraint problems.

[@magie3490]

@@Majromax but isnt that te goal? Overlaping grids mean they depend on eaxh other. Meaning if you start comparing to overlapping grids you ll find out that there are only so many states these grids can take so that there are both still able to hold there state. Either dead or alive in the present. If you repeat this for every overlapp in case there exsists a pre state to the current state of the cellular automata, you would be left with a distribution of possible states vor every grid. Now you can start collapsing

[@acters124]

This is the best video on machine learning and how the LLMs work! AMAZING!

[@MrGryph78]

No wonder it took so long, you used Python!

[@jrobwhydidyoutubechangemyname]

My layman takw on this whole amazing video is: when you're untangling electrical cables/rope/netting, sometimes you need to make it more chaotic before knots will come loose.

[@LunicLynx]

It actually simple. Just reverse the animation. 🙈 .... joking

[@Т1000-м1и]

It was an interesting thing to discover that "blockus tile" pattern as a kid

[@shauas4224]

Im completely shocked it turned out to be even remotely possible tbh. Insane work, cant wait for the next video

[@DavidPHH]

I love this channel. Thank you for the effort you put into these videos

[@speedyJ0hnny]

This is awesome, I always love your vids! looking forward to part 2 :)

[@michaeltraynor5893]

My first software job was at the company that convinced Microsoft to open-source Z3 :) we used it to find bugs in aerospace designs

[@ts4gv]

26:05 by hexagonalizing the banquet table problem you've made it CGP-complete.

[@bencheevers6693]

Eagerly waiting on the next, that teaser seemed really interesting

[@hookumsnivey1696]

I made a “Pong Shader” where going through either goal just incremented the entire screen to the location where the score was displayed correctly. It wasn’t actually allocated. The score was just a set of rules defining its coordinate display.

[@The-EJ-Factor]

6:03 this seems similar to situations like anti derivatives where data is lost during a derivative such as any constant, and are unable to retrieve the constant that was lost, which is why with anti derivatives you add a character that represents a constant such as c. To make it more understandable, generally if a*b=c then c/b = a. But if you multiply a number by 0 it would become 0 and you can’t use 0/0 to return it back to its original number.

[@The-EJ-Factor]

This is also why 0/0 is undefined rather then 0,1 or infinity. Even when you look at the rules 0 divided by any number is 0 Any number decided by itself is 1 And you can make a equation that uses limits to basically “prove” that 0/0 = any number

[@estes_was_here]

As a kid i would hand draw conways game on graph paper because i didnt have access to a computer. I read about it in a book on novel mathematics from the library. This video is wonderful