Jailbreaking in 2023 is made with natural language processing
Disclaimer
This introduction story is way more complex and nice than what’s written here, but I went towards a simple beginning. The different beginnings cointans: J. might have not said those words, I might have not said those words, or this never happened.
Introduction
I was walking in circles and writing poems in the corner of my jeans, when someone approached me, half way from the chair to another circle. I stopped the song (intp leya) to be questioned from the voice of this new soul, called J. and hear one of the 7 cardinal sins:
-Do you know about Sudoku? (or something about it)
With thousands of answers floating in my brain, one comes out from my mount though, and is “yes” (hopefully I said that instead of “i know everything”).
I approached and got shown a weirdly shaped sudoku, written and printed for mass-production of errors and broken hopes. J. wanted to learn how to pay attention (and have fun with Sudokus, but I didn’t really care about that part). And she wanted that 9x9 solved. I immediately understood the importance of the ink printed in those pale flat trees, and I did the thing that I do best. I politely explained:
-J. Do something else, that’s crazy, learn to play an instrument if you want to pay attention, or play being a shepherd dog for chairs.
After explaining my fractured theory of how music can help with logical reasoning, showed a cool musician that I know, J. was still convinced that Sudoku is the perfect training tool for her needs, or maybe not, I don’t know exactly what was in her head. I was not convinced, and I wanted to argue with her. So I started to think about it, and I come with the idea of writing something about it.
The interest from J. about Sudokus, how she envisioned it, motivated me more to find a solution to her struggle and why I don’t consider them the best result to learn how to pay attention. I thought to approach the Sudoku that she showed me, and try to find a solution to it, and then, try to find a solution to the problem of Sudoku, and then, try to find a solution to the problem of logic, and then, probably going crazy.
I’ll try to write about it, and I’ll try to write about it in a way that I can understand it, and maybe, if I’m lucky, someone else can understand it too.
This is my attempt to solve something without actually solving it, so to later confront J.’s way vs my way. One seems to be learning and finding new paths, the other (mine) seems to be analyzing, creating and distructing systems.
Sudoku, an illogic approach
Here I criticize the notion of “logic” or “systematic process” and i’ll attempt to deglorificate it. I’ll analyze the meaning of attention, power of probability, and the stupid thought that it’s better to know than to guess (this, for example comes because J. wanted to know how to solve sudoku, cause she thinks knowing stuff is cool, well, if knowing stuff was cool, J., now I would have been way more famous)
I’ll start from the wikipedia definition of Sudoku, which is referenced as a “logic-based” game.
What is Logic?
Logic it’s a complex word that captures many different meanings depending on who you ask. It is heavily encompassed in some types of philosophy, and for some it’s what distinguishes Humans from other Animals. Thanks to logic, some people could see themselves as more intelligent than a pig as they are not eating whatever someone is throwing at them. Others, can see themselves as more intelligent than poor people, simply thanks to the overcomplex amount of social rules that they need to follow in a dîner de gala. Logic seems used, sometimes, as a way to divide weirdly haired beings from animals, and people from other people. But let’s put a definition on it, just to agree on common ground, we can’t speak about how it is misused without understanding what’s the scope of it. Logic is a systematic process that can be expressed in booleans. Pretty stupid, if you think about it, everything answers to logic (or not) even the pig that you throw something at.
I use the pigs, as when I was little I threw a rock.
This rock, to my surprise, was eaten and puked back from a pig, and for each time that it was puked away, another pig approached to do the same thing. It was my first ouroboros. If you think about it, I can express in a “logical” way what the pigs did:
- -> Is that an object that flies from a person that usually throws food at us? If yes, eat. If not, keep asking yourself why you are there (I guess)
So we can see, pigs are logical, but when you think about logic, most of the people don’t think about pigs or animals, they think about humans, or “rationality”.
Wait a second, did I say that everything answers to logic? It is actually “kindish doesish”. Everything answers to logic before, and after. Not in the moment, in the moment logic is, by definition of its systematic approach, not existent. Logic is a process. When it becomes a result, it’s due to it being calculated. Is the calculation always logical? Not really, calculation needs to have a probability for it to be real (and in some cases, effective), less probability you insert in the calculation, harder (or impossible) might become the result. Yes, you can say that for each time I calculate 2 + 2, it will come to 4. But this is not the case, there will always be a probability of it having another number, independently for how little it will be. This notion doesn’t get pushed enough, as it might confuse people, but reality is pretty confusing for Sapiens Sapiens.
My thought is to consider the universe in which I am writing these words, a semi-probabilistic one at its core, or, extremely hard to compute with current technologies. I choose a semi-probabilistic approach, because I do believe probability and determinism exist only where an outcome is uncertain or certain, and as we explore the subatomic world, we are believing that it’s compromised by some probabilistic interest. This, though, doesn’t neglect another layer of determinism behind this, and even though its existence challenges our notions, it should not be out of the equation. In other words, logic breaks. And it breaks really often. It breaks in the subatomic world, it breaks in the creation of Strange Matter and it breaks in black holes. But it also breaks into how the universe started. Logic is a constraint, it’s a mere playground of thoughts, and it should not be the final ending (even if, it might be easier to accept logic reasoning, than illogic reasoning, this it’s very easily shown by the amount of people having weird sensations when explaining quantum physics, or when I approach to them).
Logic is not a building block of our Universe.
Okay, now that I barely explained that logic is not the core of this world, let’s imagine that in the sudoku example, the systematic approach is what makes it seductive for some, and the ability of solving a “semi” incognito x with a bunch of triangular lines is cool and makes someone more “observant”. (I say semi as the sudoku is not really incognito, as it’s a puzzle that has a solution, if it’s unique.)
Let’s discuss the algorithmic process of solving a Sudoku.
A Sudoku puzzle is created, first, by creating the result. Then, the result is broken into 9x9 squares, and then, the squares are broken into 3x3 squares. Then, the 3x3 squares are filled with numbers, and then, the numbers are removed in a way that the puzzle can be solved.
Some Sudokus that accepts one and only one solution, and other that have multiple solutions. The first ones are called “unique” and the second ones are called “ambiguous”. Creating an algorithm that never guesses, is not possible in the case of ambiguous puzzles. Considering the Sudoku that I received, it was ambiguous, and it was necessary to guess, even though some guesses are more probable than other, the risk is still there. Here we can see how the “logic” of the Sudoku (ambiguos) is not really a logic, but a probability. The probability of a number being in a square is not 100%, but it’s not 0% either. It’s a probability, and it’s a probability that can be calculated.
Now, that we divided Sudokus solutions in 2 group, let’s see different alghoritms to solve Sudokus.
“The general problem of solving Sudoku puzzles on n2×n2 grids of n×n blocks is known to be NP-complete. Many computer algorithms, such as backtracking and dancing links can solve most 9×9 puzzles efficiently, but combinatorial explosion occurs as n increases, creating limits to the properties of Sudokus that can be constructed, analyzed, and solved as n increases. A Sudoku puzzle can be expressed as a graph coloring problem. The aim is to construct a 9-coloring of a particular graph, given a partial 9-coloring.” (from wikipedia)
One is by using Graph Theory, another with backtracking, and another with Dancing Links. There are still many other ways, more or less efficent.
With Graph Theory:
Graph theory concepts can be applied to Sudoku by representing the puzzle as a graph where the vertices are the cells and the edges connect cells in the same row, column, or subgrid.
Here are some specific ways that graph theory concepts can be applied to Sudoku:
Degree of vertices: The degree of a vertex in a Sudoku graph is the number of edges that connect it to other vertices. In a Sudoku graph, each vertex has degree 20, representing the fact that each cell is connected to 20 other cells in the same row, column, and subgrid. By analyzing the degrees of vertices, it is possible to identify cells that have more or fewer possibilities than others, which can help to eliminate possibilities and narrow down the options.
Cliques and independent sets: A clique in a Sudoku graph is a set of vertices that are all connected to each other by edges. An independent set is a set of vertices that are not connected by any edges. By analyzing cliques and independent sets, it is possible to identify cells that must contain certain values or cells that cannot contain certain values.
Coloring: Graph coloring can be used to represent the possible values for each cell in a Sudoku puzzle. Each vertex in the Sudoku graph can be assigned a color that represents a possible value for that cell. If two adjacent vertices have the same color, it means that they cannot both be assigned that value in the solution. By applying graph coloring techniques, it is possible to eliminate possibilities and identify cells that must contain certain values.
Paths and cycles: Paths and cycles in a Sudoku graph can be used to identify cells that must contain certain values or cells that cannot contain certain values. For example, a cycle of length 3 in a row or column indicates that three cells in that row or column must contain three distinct values. By analyzing paths and cycles in the Sudoku graph, it is possible to eliminate possibilities and make progress towards finding the solution.
Graph theory to Sudoku help to identify patterns and relationships between cells that can be used to eliminate possibilities and narrow down the options. However, these techniques may not always be enough to solve a Sudoku puzzle without additional strategies and techniques.
Here a code that uses Graph Theory to visualize the Sudoku:
1
2import numpy as np
3import networkx as nx
4import matplotlib.pyplot as plt
5
6
7def create_sudoku_graph(sudoku_values):
8 G = nx.Graph()
9
10 for index, value in np.ndenumerate(sudoku_values):
11 row, col = index
12 node = (row, col)
13 G.add_node(node, value=value)
14
15 # Connect to other nodes in the same row and column
16 for i in range(9):
17 if i != col:
18 G.add_edge(node, (row, i))
19 if i != row:
20 G.add_edge(node, (i, col))
21
22 # Connect to other nodes in the same subgrid
23 subgrid_row, subgrid_col = row // 3, col // 3
24 for i in range(3):
25 for j in range(3):
26 neighbor_row, neighbor_col = subgrid_row * 3 + i, subgrid_col * 3 + j
27 if (neighbor_row, neighbor_col) != node:
28 G.add_edge(node, (neighbor_row, neighbor_col))
29
30 return G
31
32
33def visualize_sudoku_graph(G):
34 pos = {(row, col): (col, -row) for row in range(9) for col in range(9)}
35 labels = {node: G.nodes[node]['value'] if G.nodes[node]['value'] != 0 else '' for node in G.nodes}
36 nx.draw(G, pos, labels=labels, node_color='lightblue', with_labels=True, node_size=800, font_size=12)
37 plt.show()
38
39
40sudoku_values = np.array([
41 0, 0, 0, 0, 2, 0, 0, 0, 0,
42 0, 0, 0, 5, 0, 8, 0, 0, 4,
43 0, 0, 0, 9, 0, 6, 2, 0, 0,
44 4, 8, 0, 0, 0, 0, 0, 7, 5,
45 0, 3, 0, 0, 1, 0, 0, 8, 0,
46 1, 6, 0, 0, 0, 0, 0, 3, 2,
47 0, 0, 0, 3, 0, 4, 6, 0, 0,
48 8, 0, 0, 1, 0, 2, 0, 0, 9,
49 0, 0, 0, 0, 7, 9, 0, 0, 0
50]).reshape(9, 9)
51
52sudoku_graph = create_sudoku_graph(sudoku_values)
53visualize_sudoku_graph(sudoku_graph)
In sudoku, logic formulas are linked to the problem, and finding those logical formulas is more similar to travel back in time, or finding conditions to make the logic that was established true.
Let’s discuss computational complexity with a focus on protein folding:
Computational complexity is a measure of the resources an algorithm requires to solve a problem. Time is the most common measure, but it can also include memory, disk space, and other resources. Humans excel at certain tasks that are very difficult for computers, such as running, speaking, or recognizing faces. However, we struggle with tasks that computers find relatively easy, like multiplying large numbers or rapidly searching large databases.
Protein folding is a prime example of a complex problem where humans can outperform computers. Proteins are long chains of amino acids that fold into specific three-dimensional structures, which determine their functions within the body. Predicting the final folded structure of a protein from its amino acid sequence is an NP-Hard problem, which means it is computationally very challenging.
On the website fold.it, users can interact with proteins and attempt to fold them into the most energetically favorable configurations. The platform provides an intuitive interface that allows users to manipulate the protein structure, guided by their spatial intuition and pattern recognition skills. This approach has led to several successful instances where human players have outperformed computer algorithms in folding proteins:
In 2011, Foldit players helped solve the structure of a protein related to HIV. This protein had stumped scientists for over a decade, but the Foldit community managed to solve it in just a few weeks. In 2020, during the COVID-19 pandemic, Foldit players collaborated to predict the structures of proteins associated with the SARS-CoV-2 virus, which helped researchers understand the virus and develop potential therapies. Despite their success in protein folding, humans still face challenges with more straightforward tasks, such as multiplying 4.2137 by -42. This contrast highlights the unique abilities and limitations of human cognition compared to computer algorithms.
In conclusion, protein folding showcases how humans can excel at solving complex problems, especially when these tasks involve spatial reasoning and pattern recognition. The Foldit platform demonstrates how engaging and intuitive interfaces can harness human intuition to tackle challenging computational tasks, even when they are NP-Hard problems.
NP-Hard problems:
When people talk about the P vs. NP problem, they often relate NP tasks to creativity. They say that composing a Mozart-like symphony (similar to an NP task) seems much harder than checking if an existing symphony is Mozart-like (similar to a P task).
But NP seems more about logic and left-brained thinking than creativity. Think of problems like solving math equations, designing a bridge, or completing a Sudoku puzzle—these are more logical, left-brained tasks that are easier to check for quality than, say, a poem or a piece of music.
NP is mainly linked to “puzzles” (for example, Sudoku, Minesweeper, and Free Cell are all NP-complete when you generalize them for bigger sizes). PSPACE, on the other hand, is linked to “2-player games” (like chess and Go, which are PSPACE-complete). This isn’t a new idea.
People can usually solve small, finite versions of NP-complete puzzles, like a regular Sudoku grid, and still find them fun and challenging. PSPACE-complete games, like chess or Go, are often considered more difficult intellectual tasks. This suggests that PSPACE is getting close to the limits of what we can handle. However, we usually play these PSPACE-complete games against other people or imperfect computer opponents, which raises questions about how powerful interactive proofs can be when players have computational limitations.
To some extent, the sizes of actual puzzles and games are designed to match our abilities. For example, 4x4 Sudoku is too easy and boring, while 16x16 Sudoku takes too much time. So, 9x9 Sudoku is the perfect size for most people. The same idea applies to the sizes of Go and Chess boards.
Computing a 6x6 permanent by hand is another example of a difficult task. The main point is that when it comes to problems in classes way above PSPACE (or EXP), the instances that humans can solve are usually too small and uninteresting. On the flip side, for problems in EXP, any problem size below the “heel of the exponential” has a chance of being solvable by most people within a reasonable amount of time.
As for the rest of the Polynomial Hierarchy (PH), there aren’t many (if any) natural games with a fixed number of rounds. This is connected to the fact that we don’t know many natural problems that are complete for higher levels of PH.
When it comes to using randomness in Polynomial-time approximation schemes, there are two types of approximation schemes for NP-hard problems: deterministic and randomized. Fixed-Parameter Tractability (FPT) plays a role here, mainly because some problems naturally have more than one “input size” associated with them.
Let’s dive deeper into the world of math to understand the concept of “hardness.” It’s a term that brings together various ideas about comparing problems based on how flexible their algorithmic solutions are. Simply put, a problem is considered hard when an algorithm that solves it can be easily adapted to solve any problem within a specific group. It’s important to define the types of transformations allowed, which might vary for different problems in the group, but that’s the main idea.
Imagine the Super Mario example, where your goal is to solve logical formulas. You could turn a perfect mario-level-playing algorithm into a logic solver by turning the formula into a level and then letting the mario-level-playing algorithm do its thing. Add a simple “if” statement at the end to change “level can/can’t be finished” into “formula can/can’t be satisfied,” and you’re done. For NP-hardness, it’s important that this transformation happens in polynomial time. Different levels of hardness might need more or less resources.
That’s why Super Mario is considered NP-hard – because boolean logic satisfiability is also NP-hard. Any problem in NP can be solved by a boolean logic solver, and so, by a mario-level-player too. It’s pretty tough to prove that boolean logic solving is NP-hard. But if we assume it’s true, you can mix these transformations to connect any NP problem to Super Mario.
Sudoku is another example that’s linked to computational complexity. It’s been proven that solving a Sudoku puzzle is an NP-complete problem. This means it’s as hard as the toughest problems in the NP category, and if we could find a polynomial-time algorithm to solve Sudoku, it would mean P = NP. However, just like with Super Mario, the overall hardness of Sudoku doesn’t always equal the difficulty of solving individual puzzles.
Sudoku puzzles come in different shapes and sizes, with varying levels of difficulty. The most common Sudoku puzzles have a 9x9 grid and are made to be solvable by humans using logic. There are fast algorithms and shortcuts that can solve these puzzles and even harder ones in no time. In real life, the difficulty of Sudoku puzzles for humans and the complexity of solving them using algorithms aren’t directly connected. Humans are usually good at spotting patterns and can use logic to solve moderately hard Sudoku puzzles, while computers can quickly solve even the most complicated Sudoku puzzles using brute-force search or other algorithmic techniques.
So, even though Sudoku is an NP-complete problem in its broadest sense, this complexity doesn’t stop humans or algorithms from solving real-world examples. This shows that a problem’s theoretical complexity doesn’t always equal its real-life difficulty, and that clever or specialized approaches can be used to effectively solve hard problems.
PSPACE
Imagine PSPACE as a vast library that stores decision problems, which are questions with a simple yes or no answer. These problems can be solved by a librarian who has limited shelf space (memory) but plenty of time. The amount of shelf space the librarian can use is based on the size of the problem and is limited to a reasonable amount, growing no faster than the problem size squared or cubed, for example.
Now, picture two different librarians. One is a very organized and methodical worker (deterministic), and the other is an adventurous worker who likes to explore different paths (non-deterministic). Despite their differences, they can both handle problems that need a limited amount of shelf space. Surprisingly, they’re equally good at managing these problems. This unexpected equality is known as Savitch’s theorem.
The PSPACE library contains smaller rooms, like P and NP, which have their own unique decision problems. P represents problems that the librarian can solve relatively quickly and efficiently, while NP contains problems that are easy to check but may take a long time to solve. PSPACE is like the parent of these rooms, encompassing both P and NP. However, it’s still a mystery whether PSPACE is equal to NP or if it holds even more challenging problems than NP.
In the PSPACE library, some problems are considered “PSPACE-complete.” These are the toughest, most intricate puzzles in the library. If someone finds a quick way to solve any of these puzzles, it means they’ve unlocked a fast solution for all the problems in PSPACE.
PSPACE problems can be like mind-bending riddles or complex, multi-layered board games. While they can be more challenging than problems in P or NP, their difficulty varies depending on the specific riddle or game and its size.
REAL AND NOT REAL IN SUDOKUS
ABSTRACTION AS A FORM OF ATTENTION
Gaussian elimination is a widely known technique for solving linear systems of equations. It works by transforming these equations into a standard representation, a triangular matrix, which makes it easier to find the solution. In the same way, for systems of polynomial equations, there’s a normal form called the Gröbner basis. Buchberger’s algorithm helps to compute this Gröbner basis, and it can be seen as an extension of Gaussian elimination. In fact, these two algorithms are identical when it comes to linear equations. So, using Buchberger’s algorithm to find the Gröbner basis of the equations, we can determine the solution to a Sudoku puzzle.
To better understand the connection between Boolean logic, NP-hardness, and the Boolean satisfiability problem, let’s consider the power of abstraction and its role in enhancing our problem-solving abilities. For example, Gaussian elimination and Buchberger’s algorithm are used in the context of solving linear and polynomial systems of equations, respectively. The same idea of abstraction can be applied to Sudoku puzzles.
When solving Sudoku puzzles, the process involves going from handling one-to-one relationships, such as filling in a single cell, to one-to-many relationships, like recognizing patterns that can help solve multiple cells at once. Mastering this skill requires a deeper understanding of abstraction, which allows us to develop a single strategy or formula that can tackle various problems. This versatility is what distinguishes champions - their capability to address multiple challenges using a single, adaptable approach.
Abstraction can be considered a form of focused attention. Learning to solve a specific problem, like a Sudoku puzzle, can lead to discovering general patterns that apply to a wider range of challenges. This transition from one-to-one, to one-to-more, and finally to one-to-many, is a crucial element of expert problem-solving. It serves as the foundation for achieving mastery in any field, such as becoming a Sudoku champion.
INCREMENTAL AND DECREMENTAL TASKS
Incremental tasks in AI refer to those that involve step-by-step problem-solving, where each step builds upon the previous one to reach the final solution. Discontinuous tasks, on the other hand, involve solving problems by considering multiple possibilities or probabilities, and potentially making jumps between different solutions without a clear step-by-step progression.
Solving Sudoku puzzles without guessing can be seen as an incremental task. This approach requires applying logical reasoning to fill in the cells step by step, based on the constraints of the puzzle. Each step builds on the information obtained from the previous steps, gradually completing the puzzle in a systematic manner. This is a common method employed by human solvers and some algorithms designed to mimic human-like problem-solving.
Using probability theory to solve Sudoku puzzles is more similar to a discontinuous task. This approach involves exploring different possibilities for each cell based on probabilities, and then making educated guesses to fill in the cells. It might require backtracking if a guess leads to an invalid solution, or jumping between different solutions without a clear step-by-step progression. This method is more commonly used by algorithms that employ techniques like constraint satisfaction, backtracking, or search strategies to find a solution.
In general, the harder the Sudoku is, the more likely it is that guessing and backtracking will be necessary to find the solution.