P vs. NP: The Biggest Puzzle in Computer Science
Vložit
- čas přidán 9. 05. 2024
- Are there limits to what computers can do? How complex is too complex for computation? The question of how hard a problem is to solve lies at the heart of an important field of computer science called Computational Complexity. Computational complexity theorists want to know which problems are practically solvable using clever algorithms and which problems are truly difficult, maybe even virtually impossible, for computers to crack. This hardness is central to what’s called the P versus NP problem, one of the most difficult and important questions in all of math and science.
This video covers a wide range of topics including: the history of computer science, how transistor-based electronic computers solve problems using Boolean logical operations and algorithms, what is a Turing Machine, the different classes of problems, circuit complexity, and the emerging field of meta-complexity, where researchers study the self-referential nature of complexity questions.
Featuring computer scientist Scott Aaronson (full disclosure, he is also member of the Quanta Magazine Board). Check out his blog: scottaaronson.blog/
Read the companion article about meta-complexity at Quanta Magazine: www.quantamagazine.org/comple...
00:00 Introduction to the P vs NP problem
02:16 Intro to Computational Complexity
02:30 How do computers solve problems?
03:02 Alan Turing and Turing Machines
04:05 George Boole and Boolean Algebra
05:21 Claude Shannon and the invention of transistors
06:22 John Von Neumann and the invention of the Universal Electronic Computer
07:05 Algorithms and their limits
08:22 Discovery of different classes of computational problems
08:56 Polynomial P problems explained
09:56 Exponential NP Problems explained
11:36 Implications if P = NP
12:48 Discovery of NP Complete problems
13:45 Knapsack Problem and Traveling Salesman problem
14:24 Boolean Satisfiability Problem (SAT) defined
15:32 Circuit Complexity Theory
16:55 Natural Proofs Barrier
17:36 Meta-complexity
18:12 Minimum Circuit Size Problem (MCSP)
- VISIT our Website: www.quantamagazine.org
- LIKE us on Facebook: / quantanews
- FOLLOW us Twitter: / quantamagazine
Quanta Magazine is an editorially independent publication supported by the Simons Foundation: www.simonsfoundation.org/ - Věda a technologie
Read about about "Complexity Theory’s 50-Year Journey to the Limits of Knowledge" at Quanta Magazine: www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/
Confused Here... Please Help... ????
First Statement of Logical Facts and Action in the Video...
""A Robot arrives in a foreign land where everyone either always tells the truth or always lies. The robot reaches a fork in the road with two choices. One path leads to safety in the land of truth tellers, while the other leads to doom in the land of liars. A sentry appears. But it is unclear which group they belong too."" What question can the robot ask to determine the safe route."
Q1. Which path leads to the land of liars?
Q2. Are you a liar or a truth teller?
Q3. Which path leads to your home?
Number 3 is the videos answer to robot's quandary... But WTF? THE SENTRY COULD BE LYING AND POINTING OUT THE WRONG PATH TO HIS HOME.... SINCE HE COULD BE FROM THE LIARS GROUP.
How does the video factually, logically, conclude from the stated logic RULES prior to the tested answer... That it is SAFE to go right. Why is it safe to go right.
HELLO ?
I don't see the robot being able to correctly draw a conclusion from the facts give up to that point ?????????
So how can we move on to multiple sentries if the prior action is based on a logical fallacy ????
As a CS graduate student, the theoretical sections of the field are quite mind-bending and very profound in a way. I thnink often times people underestimate what deep insights questions in computer science can give back to the world. Thank you for showing such a nice summary of one of them!
Yes. People assume human creations are somehow unnatural, but many if not all are an interation of natures patterns. We have an innate desire to express them, or their expression is just inevitable. The further we go the more we realize we are just creating something already created. In a way, unraveling the story the universe is trying to tell us.
In Sha Allah you will solve this
I think Theoretical Computer Science is as fundamental to the nature of the reality as Physics. These days more and more physicists look at problems through the lens of information theory and computational complexity.
@@test-zg4hv Wait when did we get sex robots? Where can I buy one right now? 😅😁
@iamtheusualguy2611 Absolutely. When I started studying CS I had a hard time with mathematics and didn't see much use of all the theoretical parts. But it didn't last long until I've seen the wonders of Logic, Complexity- and Computability-Theory. I consider them the absolute highlights of my time at university, and it often felt like some kind of mathematical philosophie, so deep were the results I learnt there.
I wish more people would know about the deep wonders of theoretical computer science.
I might take a crack at this on a chalkboard while I'm working my janitor job at MIT
You would fail....
@@weqe2278just like you failed at getting the joke
Go for it, Will.
Good, Will
@@weqe2278How do you like them apples! 🍎
This video is good, but a few small details to add.
1. Solving P vs NP doesn't mean all encryption breaks overnight. RSA encryption could be broken if a polynomial algorithm is found for an np complete problem, but only if the polynomial isn't too big. Even polynomial algorithms can be unusable in practice. This is all assuming an explicit constructive proof P = NP is found. Non constructive proofs will not help solve any of the real world problems, and if it is shown P is not equal to NP, nothing will change. Even if an algorithm to break RSA is found, we can build other encryption methods using NP Hard problems like Travelling Salesman Problem (shortest path version).
2. The Travelling Salesman Problem (TSP) is NP hard in it's usual statement. It is only NP complete if you ask the question "is it possible to find a path that is shorter than a given length". If you ask the problem of finding the shortest path, this is not verifiable in polynomial time.
If TSP Shortest Path is NP-Hard due to the complexity of verifying a solution, wouldn't that render it unusable for encryption, as quick verification is a requirement?
@@TheEzypzy No. If you actually know the solution, it is easy to verify. If you do not know the actual solution, it is hard to verify if a proposed solution is actually a solution. If I know the actual shortest path, it is easy to see if someone else found the same shortest path.
What is hard is if I do not know the shortest path, but I have a pretty short path, how do I ensure it is actually shortest.
@@patrickgambill9326how do you verify(for yourself or others) the answer you claim to be correct is actually correct
yeah you're right:) Like the proof that LPs can be solved in poly time:)
Its nice to know but the algorithm is unusuable compared to the Simplex Alg:)
I think RSA is Co-NP not NP and can be solved by Shor's Algorithm in polynomial time, but more recently there have been proposals for quantum safe cryptography that use random walks in higher dimensions with secret basis vectors, I think.
Turing was brilliant and saved untold lives in WWII with his encryption work. How they treated him was horrible.
I agree with u, The Imitation Game tells it.
What? He didn't save any lives in WW2
@@bennyklabarpan7002 Many, many lives were saved because of Alan Turing and his team in breaking the Enigma code.
@@reh3884 Not at all, it just prolonged the war
@@bennyklabarpan7002 still doesn't change how much he contributed to science
So glad to see Shannon mentioned. He is massively underrated, he basically is the father of modern computers (let alone Communication and Information Theory)
If I was ever getting a tattoo, it would be the formula for entropy
This was excellent! Scott Aaronson praised it highly for accuracy but did state that it would have been improved by addressing the difference between Turing machines and circuits (i.e., between uniform and non-uniform computation), and where the rough identities “polynomial = efficient” and “exponential = inefficient” hold or fail to hold.
Clearest explanation I’ve seen. Maybe it could’ve been paced slightly slower at points but nothing a manual pause and rewind won’t fix.
His last question "Will we be able to understand the solution?" is the most profound question of all.
It reminds me of the computer "Deep Thought" in "The Hitchiker's Guide to the Galaxy" which spent generations trying to solve the problem of "Life the Universe and Everything".
After many hundreds of years it came up with the answer.....42.
But what does THAT mean ????
42 just means that author of The Hitchiker's Guide to the Galaxy ran out of ideas what to write so he thrown a dice and put down the value he got.
Exactly! Let's say that matter and energy sprout out of nothing, and both can cancel out. What made them separate to start with, and rejoin later? c? the speed of light? c can survive any black hole, but we can't appreciate the speed of light as a "thing". So 42 could be an answer but we can't understand that as a solution.
It means that the person who posed the question and the brainy computer were functional idiots. Garbage in and out. In other words, bad question, bozo.
It's always about semantics, isn't it? 💀
Im a teacher and I have to applaud your video style. It's excellent from an educational perspective with very sharp and clear visualisations and superb pace. Bravo.
I love how he says 'if humanity survives long enough'. Great reminder, we really need to do better.
I'll get right on it 😉
What a well constructed video. I appreciate how it went from basic Computer Science knowledge and gradually introduced higher level Computer Science topics in a simply put way.
Watching a video on advanced computer science topics and not knowing how to adjust the playback speed on youtube is making me laugh
Best video I’ve seen in a long time. Honestly. Great, on the point presentation of distinct very important, fundamental concepts of our time
One of the best explanations of P, NP. I recalled my Theory of Computation, Information Security lectures and found it really fascinating. The insights are really cool and best explained. Thank you so much !!!
Did NOT expect a Boolean logic primer in a P versus NP video. 🎉
Phenomenal visuals and amazingly concise definition. Simply beautiful.
Its mind boggling how many consistently great videos Quanta Magazine puts out frequently. Thank you for this gift to the world.
lol settle down
@@codycast no thanks
Im an electrical engineering graduate besides understanding in electricity what really shakes me is understanding of how computer thinks. I really love it as side hobby. 😊
I briefly dabbled into this topic in a Computer arithmetic hardware implementation course that I took in grad school ( MS Microelectronics Engineering) . Mainly the part on circuit complexity ( as that was the applicable concept to the course).
It’s was a really interesting topic/course, especially the part of the course where I got to optimise a hardware implementation of an FFT algorithm on an FPGA by applying the techniques in the course.
Thanks for this, when I took computer science classes at UTD, this was glossed over in a slide, and given maybe two sentences in the textbook.
This is an amazing video, I'm really impressed by the quality of the animations and explanations. Thank you for putting the time in to make this!
the quality of these videos is so incredible
This video greatly overblows the real-world significance of P vs. NP. The question is a very theoretical one and, although it would be unintuitive to learn that P = NP, it is by no means a given that a proof of P = NP would leap down from the ivory tower and cause any direct or "overnight" effect at all on the internet, AI applications, business, cryptography, etc. For people other than academics to care, we would need to see new algorithms that are actually greatly more efficient on real-world problems than current real-world approaches are, but no such algorithm is necessarily provided by a proof in this area regardless of its conclusion.
A proof doesn't even prove that such algorithms exist. P == NP is not the same thing as P-with-very-small-exponents == NP.
It could be that the knapsack problem is in P because someone finds an O(n^10,000,000) algorithm. This would be a constructive proof that P == NP but also have essentially no practical implications.
2:17 study of inherent resources, such as T & S needed to solve a computational problem
woah woah, so precisely put definition. awesome.
I have discovered that some programs have parts of code of P class and parts of code of NP class. There are classes of relaxations that use heuristics that can solve some problems but with no warranty about its success or about its optimality.
You’re video is great. My professor was talking about this in class, and you went into so much detail. I like the parts you included with the other guy too. The back and forth was cool!
Thank you for a great explanation of p vs np! Never got it during my computer science studies
who made the animation in this video is a genius. As well as the people behind the script!! Great job!
Best video ever on the topics of explaining P vs NP problem
it's fun looking into the CSAT problem and trying to figure out exactly why you can't just assume the output to be 1 and trace it back to a random possible input combination.
It eventually comes down to these two facts:
-----------------------------------------------------------------------
1. logic gate outputs can get shared between logic gate inputs.
E.g: say, the output of an OR gate is connected to 2 (or more) AND gate inputs.
2. Logic gates AND and OR have multiple inputs mapped to their outputs. This means, they are many-to-one functions and do not have inverse functions. As a result, when you try to trace back from a given output, you have to randomly guess an input every time. This wouldn't be a problem on its own but due to our first point (logic gate outputs can get shared between logic gate inputs), when two guessed inputs end up meeting at a common output, they won't necessarily match so you end up with 1 and 0 being output value simultaneously.
And that's where the computational complexity increases drastically, because now you have to keep an account of all those common outputs branching into multiple inputs, so that your guessed inputs align when they meet there.
There are some contradictory statements in your video, but it is a great presentation of N and NP problems. Thank you for creating such a wonderful explanation in layman's terms.
I just saw Scott Aaronson 5 days ago (when this was released) at UT and studied P vs NP. nice timing
this
is
QUANTA
truly thanks for this amazing summary!
Thank you for imparting this knowledge to me.
This was an amazing video. Thank you!
Talking about this stuff reminds me. I think the SAT Solver progress is heavily undersold. both as a technical progression, but it is really, really useful. would love a crash course. thx
Great quick explanation of SAT! Not as easy at it looks.
Absolutely fascinating video, animators deserve a raise
On it ..
I think an important point to be made in the field of algorithms is that a lot of the efficiency of certain algorithms depends on input size.
Theoretically, if you have a P problem and an NP problem that solve the same problem, the P problem runs in n^200 time whereas the NP problem runs in 2^n time, if your input size is always small, say 2 or 3, then actually the NP problem is more efficient.
You can also apply this idea to just the area of P problems - for example with sorting algorithms, if we know the input size will always be very small, sometimes it is more efficient to use what is learned as the “slow” algorithms (like selection sort/ bubble sort) vs the “fast” algorithms like merge sort or quicksort. Some may argue this can’t be since bubble sort runs in n^2 vs merge sort running in nlogn , so merge sort is always at least as good, however there are also hidden constants in these runtimes that get overlooked easily. You should really see the runtimes as (n^2 + c) and (nlogn + d) respectively, where c and d are constants and c < d. You can see the constants as additional overhead needed to set up the algorithm.
in academia we usually ignore the constants as n grows large, but in practice, there may be cases where n is guaranteed to be small to the point where it is actually more efficient to use the simpler “slower” algorithm. A good analogy that my professor made is why use a sledgehammer to pound in a nail when a regular hammer will do. ( this also applies to deciding which kinds of data structures to use)
Anyways nicely made video! 👍
No, it isn't.
An awesome video gave a lot of insights on the the kind of problems and it would be nice if the solutions are always used for the benefit of the society
Beautiful video; thanks for sharing.
Such a great video, learned a lot. Can I ask what tools did you use to create such graphics and videos?
Great video (as always)!
Beautifully explained
They got Scott Aaronson. Nice.
Okay, can we talk about how cool this animation is though??
I think there's a way. Consider that there could be hidden, exploitable structures or patterns in a NP-hard problem (example) that might have less time/space complexity and depends on the input size, algorithm, the exact values/order of the input, and/or more.
Beautiful work, managed to explain a very complex idea in simple terms and animation. Bravo 👏
Simple things interacting can lead to complexity and emergence, this applies to algorithms...
"Wow, imagine how many things we could do if P = NP!"
*Jevons' paradox's honest reaction:*
📝 Summary of Key Points:
📌 The P versus NP problem is a conundrum in math and computer science that asks whether it is possible to invent a computer that can solve any problem quickly or if there are problems that are too complex for computation.
🧐 Computers solve problems by following algorithms, which are step-by-step procedures, and their core function is to compute. The theoretical framework for all digital computers is based on the concept of a Turing machine.
🚀 Computational complexity is the study of the resources needed to solve computational problems. P problems are relatively easy for computers to solve in polynomial time, while NP problems can be quickly verified if given the solution but are difficult to solve.
🌐 The P versus NP problem asks whether all NP problems are actually P problems. If P equals NP, it would have far-reaching consequences, including advancements in AI and optimization, but it would also render current encryption and security measures obsolete.
💬 Circuit complexity studies the complexity of Boolean functions when represented as circuits, and researchers study it to understand the limits of computation and optimize algorithm and hardware design.
📊 The natural proofs barrier is a mathematical roadblock that has hindered progress in proving P doesn't equal NP using circuit complexity techniques.
🧐 Meta-complexity is a field of computer science that explores the difficulty of determining the hardness of computational problems. Researchers in meta-complexity are searching for new approaches to solve important unanswered questions in computer science.
📊 The minimum circuit size problem is interested in determining the smallest possible circuit that can accurately compute a given Boolean function.
📣 The pursuit of meta-complexity may lead to an answer to the P versus NP problem, raising the question of whether humans or AI will solve these problems and if we will be able to understand the solution.
💡 Additional Insights and Observations:
💬 "The solution to the P versus NP problem could lead to breakthroughs in various fields, including medicine, artificial intelligence, and gaming."
🌐 The video mentions the concept of computational complexity theorists wanting to know which problems are solvable using clever algorithms and which problems are difficult or even impossible for computers to solve.
🌐 The video highlights the potential negative consequences of finding a solution to the P versus NP problem, such as breaking encryption and security measures.
📣 Concluding Remarks:
The P versus NP problem is a significant conundrum in math and computer science that explores the possibility of inventing a computer that can solve any problem quickly. While finding a solution could lead to breakthroughs in various fields, it could also have negative consequences. The video discusses computational complexity, circuit complexity, and meta-complexity as areas of study that may contribute to solving this problem. The pursuit of meta-complexity raises questions about whether humans or AI will solve these problems and if we will be able to understand the solution.
Generated using Talkbud (Browser Extension)
Problems such as these are a wonderful conundrum for my little brain to twist and turn and loop around . . . . .
Plain Boolean formulas cannot operate like a Turing machine because they have a fixed bound on computation (once you assign values to the variables you can simplify the expression in a fixed amount of time). For a paradigm to be Turing complete it must be possible for it to run forever, which requires conditional loops. Boolean circuits can be made Turing complete by introducing registers (for memory) and a clock to synchronize computational steps, but they can no longer be represented as pure Boolean formulas.
5:25 "truth circuits" are essentially analogue neural nets that cant take into account partial voltages like digital or biological nodes can to process the input layer and calculate and output.
to add consistency: iff constructively solved with small constant/polynom to yield presented disruptions, PKI failure would be no factor anyway because zero-marginal cost economy/society equals non-monetary economy provided the materialized P=NP (non-deterministic processor (NDP)) is public domain, e.g., via IPFS
P=NP
this video is GOLD
Now this is my type of video
Excellent presentation
You packed so much info in and explained everything so well in under 20 minutes. Nicely done.
Very informative! ❤
Nice summary
Intuitively i would say, there always be problems that are two much dificult to computers to solve. There always will exist NP problems. Even with quantum computers, as computers arquitecture helps finding more complex solutions in polynomial time, it will always raise NP questions. Therefore its like solving all mysteries of life in computational time.
5:13 You'll have to amend the comment on how "Boolean boolean formulas can operate like a Turing machine." There is something to be said about representation of decision problems (computably enumerable sets being Diophantine), but a fixed circuit has a maximal number of binary inputs, while an abstract Turing machine can be initialized with arbitrary size inputs.
For as long as I've known about it the "Is P - NP?" problem has intrigued me.
A 20 minute video on P vs NP problems that FAILS to first define what P and NP actually stand for. Good job Quanta!
Having studied this before I love how well explained this is for people who have no understanding of the field.
Depending on whether or not the sentry ALWAYS tells lies, or just CAN tell lies, and whether or not you can ask multiple questions, then there can be an optimal guaranteed solution to the problem. All you have to do is ask a question with a known answer. "What is 2+2?" If they give you a false answer, then they lie, and the remaining answers just need to be inverted.
If you are limited to one question, it could be this: "If I asked the other guard which way is the safe path, what would he tell me?" Both guards would point to the unsafe route. Take the other route to safety.
I'm not sure the answer in the video is correct.
I never heared of this problem till two days ago. What a fascinating problem, as a philosopher this is as tempting as candy for a kid.
Quanta is conducting a series of surveys to better serve our audience. Take our video audience survey and you will be entered to win free Quanta merchandise: quantamag.typeform.com/video
Excellent & thanks.
Does this connect with Big O Notation and largely explain the space complexity functions deal with or are these concepts just similar?
My understanding of Big O notation is you use it to analyze algorithms by stripping away the unnecessary details and keeping the details that matter. The details that matter are what you show with Big O notation. So if you say the performance of some algorithm f with input n = n**2 + 275, the “+ 275” is really irrelevant as n gets large (the difference between 1,000 squared and 1,000 squared + 275 is trivial). So O(f) = n**2 So it is relevant because both are about the computability of an algorithm but P vs. NP describes two sets of problems with radically different performance where as big O notation is a convention for describing performance. But that’s just based on memory so I could be wrong.
A beautiful Japanese whodunit novel called "The Devotion of Suspect X" highlights this P vs. NP problem wonderfully.
best one I have seen so far regarding P vs NP
It’s not a profound problem. It’s THE most profound problem. If p =/= np, then we are essentially close to the limit and stuck until we disappear.
On circuit complexity.
Take Boolean algebra and translate it into tri part logic with logarithms. Then quad, and so on...
An algorithm having polynomial time is equivalent to the following fact:
Doubling you input will multiply the processing time by a bounded amount.
Btw, great that the video only focussed on the problem itself, not the prize money.
just one word......."AWESOME"
great explanation
If P=NP that does not mean that the polynomial time solution is within reach. Polynomials of high degree also grow fast...
Jigsaw puzzles are in P btw, specifically O(n^2).
Doing one hard puzzle might take an infinite amount of time, but running an infinite amount of hard puzzles once would give you atleast ONE solution that you can verify.
Wisdom traditions around the world have grappled with the issue.
Brilliant video. Think I understood nearly everything. Which says probably more about me than about your video, but still..... Thanks!😂
Ok, encryption is important to everybody but the best example is the 3-body problem aka 3-body instability. When you compute the future position of three bodies subject to gravitation you'll get an answer that will always have an error. So now you are searching for an algorithm that will give you zero error. This is easy for two bodies but with three (or more) bodies one must take a time increment and compute the next position at the next time increment that is also the source of the error. Further, the 3-body systems are unstable and chaotic (have no repeating period). Nevertheless you shorten the time increment and lower the error but this will take more time to perform the computation with the result that the error reaches zero when the computing time reaches infinity. Here is a good spot to see that Turing's assertion of giving the computing machine unlimited time in his definition of the universal machine --- *it does not make it universal.*
So, ending my comment right here right now is ok and we can "seriously muse" about all this. Unfortunately the cat is out of the bag and implications are fundamental (if not existential). The thing is that our solar system is said to consist of more than two bodies. Ignoring creation/evolution the solar system will break up sooner or later and even theoretically it is now teetering on the edge and can fly apart any minute. Or you can take the 3-body instability as prime reality, chuck the solar system and figure out that the Moon is not a mass rock (hologram image?). Oh, before you call me out as a flat earther, consider that the Earth, Sun, and Moon are three bodies that are working nicely together thank you.
Nice introduction, easy to follow. Like the jigsaw and Sudoku analogies. Just saying.
Nice. Well done.
There are a good chunk of standard gates, in boolean logic, but foundationally you only need 2. Not, and either and, or or. You can construct the other with these parts. Or for example is not(not A and not B) the and only returns true now if both A and B are false, meaning the whole construct becomes an or. The same trick can create and from or
Ah I like this, I remember taking my Algorithms course and being introduced to such a problem it's amazing. Thanks for the video!
good demo of the bolean cul de sac... We now need a tetravalent logic, independent of its language
The boolean logic gates helps me to understand deep learning and how a set of gates like a sigmoid or relu functions as gates that can learn if they form themselves into ai functions
Verifying a number is prime is in P (proved in 2002, Agrawal et al). A good example of a problem that regardless of being in P cannot be solved quickly. Be careful with comparing complexity classes.
thanks, I love complexity, so now I am going to research what you mean by classes of complexities!
Maybe the two scenarios has an connection to each other? Like if i have an solution or if i solved an complex problem,i would easily and more faster solve the problem.But if you had like no solution at all then it would be hard and it would take time to solve the problem? So maybe P=NP:P≠NP indicating that there's some relationship with the two scenarios?
THIS IS WHY every time 'quantum computers' make an advancement in speed on a given type of algorithm traditional programmers quickly improve on the previous system and outperform the quantum advancement. such is life.
Thanks for explaining this in a clear and chatty style.
I checked some definitions, and I think I've proven that P=NP.
I need to make sure that I haven't misunderstood the problem though, so I've written my proof out concisely, and sent it to expert friends.
... Is there some prize for doing this?
I too have a truly marvelous proof of this proposition which this comment field is too short to contain.
are you also a Nigerian Prince who needs a bank account to deposit a billion dollars into?@@ProuvaireJean
Even if P vs NP has positive solution it has just an existential nature. It does not give us a way to contract polynomial-time algorithm for any NP hard ones. There are many problems for which we have the guarantee of solution's existence but yet no one could find it. So even if P VS NP solved there is no immediate danger of losing internet or bank cash.
As Knuth says, existence doesn't necessarily mean embodiment.
I would like to read more about theoretical computer science research papers.
Where can I find information and material or content about theoretical computer science.
I would also like to know about the current ongoing research
Please share some resources about this!!
Well, proving P=NP alone wouldn't do much of what you were saying. We would still need to figure out the specific algorithms (I don't think the proof, if it exists, will also provide a template to "convert" all NP problems to P problems).
I believe the idea is that the algorithm itself is the way to prove P=NP. Another way to say it is, how could you prove P=NP without such algorithm?
I solved this problem earlier this week. I published my first rough draft earlier this week. It turns out P is not equal to NP. I have rigorously proven it using very advanced mathematics that was thought impossible to do. Amazingly, the proof shows us two amazing facts: all polynomial time problems have optimal substructure and there is an intricate relationship between mathematics we grew up learning: commutativity, associativity, and one more property: logical universality. It turns out, they don't play nice together and therefore P is not equal to NP. You can't have all three properties.
Sure you did.
@@Schnorzel1337 I found a gap in my proof, but it is not a large gap. Basically, I use two way containment to show that P is equivalent to polynomial time dynamic programming. However, one of the directions has a slight mistake in the proof. If I fix that, then yes, I will have proven it. I have spent years and years (decades now) trying to solve this problem chasing it through an amazing journey that I could write a book on. I went through group theory, ring theory, semigroups, magmas, etc.... Honestly, I thought I had proven the opposite, but I realized my attempt to prove P=NP led me to a proof of P!=NP.
"All polynomial time problems..."
By Rices theorem there is no one way to decide whether a problem is in P.
On the other hand, that's what natural proofs assume, yet natural proofs have been proven independent of P-NP.
Sorry.
The liar/truthful sentry problem has an alternative solution - the indirect "if I ask the other sentry, what would they say?", which differentiates between the binary choice required. Just a lateral thought. I do not know if there is a formal 'indirect logic' © approach to problem solving.
The "simple logic" is Superposition-point centered log-antilog relative-timing in Eternity-now, condensation, from your POV.