in computer science, we talk about a mathematical construct called a machine. Different kinds of machines can solve different problems, and the turing machine is the most powerful. It can solve any problem that can be solved by a machine.
Turing machines operate one step at a time, with each step taking the same amount of time. The total number of steps it takes to solve a problem is the time, of that machine.
Some problems have a fixed number of inputs, like “list all the states”. These machines have a fixed time. We call this constant time.
Others can have a variable number of inputs, like add up an arbitrary list of numbers. The longer the list is, the longer this takes.
An interesting, and important question is, how fast does the time of a machine go up as we add more inputs?
There are to major groups: the machines were the time goes up in a polynomial way (called P) and the ones were it goes up faster (called NP for non-polynomial). This means, for some machines, you can describe the time with an equation like time=inputs^n where n is any number.
A conjecture is that actually, all problems (that can be solved ) have a machine that can do in P time, thus all NP problems are actually P problems if we find the right machine.
This is important because much of our secret codes and other inportant things that we use today rely on those NP problems, which are really hard to solve. But if it turns out that they are P problems after all, there can be easy solutions.
In general, P = NP means that some algorithms will become much faster to solve. We have some algorithms that we depend on being hard. Most notable is encryption. We depend on it being hard for am attacker to crack the encryption (but easy for someone who already knows the answer – eg, your password). P = NP might (but not necessarily) make it easy enough for encryption to therefore be broken.
I say not necessarily because while P = NP does mean certain types of algorithms will become faster (in at least certain cases), it’s still possible for them to be quite slow. P and NP refer to how long algorithms take, based on how they scale with input. P is polynomial and NP is non-polynomial. Polynomial functions scale far better than non-polynomial functions, but that doesn’t mean they necessarily scale well, as there’s plenty of types of polynomial functions, some which scale far, far better than others.
ELI5?
in computer science, we talk about a mathematical construct called a machine. Different kinds of machines can solve different problems, and the turing machine is the most powerful. It can solve any problem that can be solved by a machine.
Turing machines operate one step at a time, with each step taking the same amount of time. The total number of steps it takes to solve a problem is the time, of that machine.
Some problems have a fixed number of inputs, like “list all the states”. These machines have a fixed time. We call this constant time.
Others can have a variable number of inputs, like add up an arbitrary list of numbers. The longer the list is, the longer this takes.
An interesting, and important question is, how fast does the time of a machine go up as we add more inputs?
There are to major groups: the machines were the time goes up in a polynomial way (called P) and the ones were it goes up faster (called NP for non-polynomial). This means, for some machines, you can describe the time with an equation like time=inputs^n where n is any number.
A conjecture is that actually, all problems (that can be solved ) have a machine that can do in P time, thus all NP problems are actually P problems if we find the right machine.
This is important because much of our secret codes and other inportant things that we use today rely on those NP problems, which are really hard to solve. But if it turns out that they are P problems after all, there can be easy solutions.
Salesmen… salesmen everywhere
In general, P = NP means that some algorithms will become much faster to solve. We have some algorithms that we depend on being hard. Most notable is encryption. We depend on it being hard for am attacker to crack the encryption (but easy for someone who already knows the answer – eg, your password). P = NP might (but not necessarily) make it easy enough for encryption to therefore be broken.
I say not necessarily because while P = NP does mean certain types of algorithms will become faster (in at least certain cases), it’s still possible for them to be quite slow. P and NP refer to how long algorithms take, based on how they scale with input. P is polynomial and NP is non-polynomial. Polynomial functions scale far better than non-polynomial functions, but that doesn’t mean they necessarily scale well, as there’s plenty of types of polynomial functions, some which scale far, far better than others.