Proving P=NP Requires Concepts We Don't Have | Richard Karp and Lex Fridman
HTML-код
- Опубликовано: 27 июл 2020
- Full episode with Richard Karp (Jul 2020): • Richard Karp: Algorith...
Clips channel (Lex Clips): / lexclips
Main channel (Lex Fridman): / lexfridman
(more links below)
Podcast full episodes playlist:
• Lex Fridman Podcast
Podcasts clips playlist:
• Lex Fridman Podcast Clips
Podcast website:
lexfridman.com/ai
Podcast on Apple Podcasts (iTunes):
apple.co/2lwqZIr
Podcast on Spotify:
spoti.fi/2nEwCF8
Podcast RSS:
lexfridman.com/category/ai/feed/
Richard Karp is a professor at Berkeley and one of the most important figures in the history of theoretical computer science. In 1985, he received the Turing Award for his research in the theory of algorithms, including the development of the Edmonds-Karp algorithm for solving the maximum flow problem on networks, Hopcroft-Karp algorithm for finding maximum cardinality matchings in bipartite graphs, and his landmark paper in complexity theory called "Reducibility Among Combinatorial Problems", in which he proved 21 problems to be NP-complete. This paper was probably the most important catalyst in the explosion of interest in the study of NP-completeness and the P vs NP problem.
Subscribe to this RUclips channel or connect on:
- Twitter: / lexfridman
- LinkedIn: / lexfridman
- Facebook: / lexfridman
- Instagram: / lexfridman
- Medium: / lexfridman
- Support on Patreon: / lexfridman 
Наука
Man I am tired but Lex you've made me go nuts for information the last few months .
Thank you for your podcasts .
you just have to prove that N = 1
@s0urid5n that would imply assuming what you want to prove
You know, you’re not wrong
Or p = 0
N stands for “Nondeterministic” so no
@@futurist1399 It's a joke.
A possible (constructive) proof of P = NP would be an algorithm that solves an NP-complete problem in polynomial time for all possible instances. Since that problem is also NP-hard all other problems in NP could be reduced to it in polynomial time and solved this way. Of course, how such an algorithm might look like is anybody's guess...
If A can be reduced to B, that means that the complexity of B is greater than or equal to that of A; reducing a problem may increase its complexity, not reduce it.
The question has a formulation error, not p = np? natural,
is, What is needed for p and np to be equal? And the answer is relativity.
@@gonzalogarcia6517 what will we achieve if this is true
@@sb.sb.sb. every answer we don’t understand or something we can’t find. Cancer cures.
Easy p2=n
@@baberhamlinkon9738 it'll have almost no impact in the near future
consigo resolver esse problema em tempo polinomial
I disagreee a bit on the impact part. If P = NP, that doesn't mean we will automatically know how to solve NP problems such as TSM or SAT in polynomial time, it only means we will know that it is possible to find these solutions in principle. Viceversa, if P ≠ NP, that doesn't have much practical impact either: while SAT is NP in theory, there are lots of SAT solvers that are good enough in practice, employing techniques such as heuristics or methods that are efficient on the average cases that you usually come up with in real life.
Wouldn't the proof in P = NP involve finding a solution to any NP-complete problem that's solved in polytime? If so, because any NP problem can be reduced to any NP-complete problem in polytime, then any NP problem can be solved in polytime.
acceptable solution is when you calculate a maximum error and from there you calculate the time taken to solve the problem then next step is to decrease the error and calculate the new time and if you see any time difference increase by huge values during this steps then stop that and take the faster solutiin as good
P=Np=#P=Pspace=#Q=Qspace for modest size (n
Hi guys, please destroy my argument and give feedback. I suppose it is as follows.
Which computational world do you think we inhabit, and why?
I think we inhabit the world they call Heuristica, that P = NP, and that cryptography will always be a fairly trivial matter of scope overflow and translation cost. My rationale is that causality is the defining characteristic of our universe, and therefore computationally axiomatic and irreducible. As described by Heuristica, it's possible to have mechanisms that approximate perfect algorithmic structure when decrypting the probability space. DNA is an example. It averages out to deterministically create the human imagination, which is limited only by scope and translation efficiency, but evolved in order to replicate the progressions of nature and physics in order to predict the next word in a sequence of words. The mind is a universe simulator, and people have called both limitless, but the seemingly non-polynomial mind is constructed from a discrete set of definitions. Therefore, if we can imagine it, it must necessarily be equal to P. Next, I would say that our imagination mirrors the causality that defines our universe. All it means for something to be real is for it to be consistent with the chain of causality. Nothingness does not exist because existence would make it a thing, which would imply causality. Causality is representable through token simulation, hence the verbal token prediction characterizing human cognition. Therefore, a thing is either representable through tokens, or it does not exist. Cryptography becomes a matter of finding the minimum energy combination of indivisible tokens to represent the probability space, like but not limited to prime numbers building the entire number line. Processes are only non-polynomial when relevant components aren't defined and sorted, but causality gives everything definition and ordinal placement.
This is a great argument. It's like the algorithmic equivalent of thermodynamics and the nonreversible arrow of time. If P=NP, time is unidirectional, there is no increasing complexity from emergence. That's a really interesting way to think about it.
The hash function for instance, which crypto uses. If P=NP, from an intuitive perspective, we ought to be able to reverse the hash function in P time. I think.
I have had that theory for years but I modified it to prove p = np by contradiction as well, with ideas such as the theoretical concept of randomness and also the the directionallity of logic. I am have currently developed a very promising and possibly decisive hypothetical algorithm for tsp but I am still developing the underlying concepts that it requires. Though my intuition for the algorithm is very elementary and can be applied to linear systems.
if( P!=NP)
{
cout
You cannot be finished with yes and no. Just confinments.
It may be that some solutions are transcendental in computational space, may have to go probabilistic and live with it or apply something outside the field currently, or invent an architecture that has a different relationship with computational space
I think the more interesting question would be how a proof of "P != NP" would look like, as it is the more reasonable option, to the eyes of most researchers.
its obviously to every person p is not equal to np. if n=np, the polynomial would have giantic constant and max degree so the algorithm is unusable in real life
proof by contradiction
@@jitenderbishnoi2016 no it'll be proof using axiom of choice. generally non constructive proofs need it to find some object with specified properties. without AC the algorithm space would be much smaller.
maybe its independent of ZFC like the continuum hypothesis.
Confused..the subtraction examples are very bad..solve this first
Ok p is competing.
If P=NP, all problems are manifestation of the same problem.
Never thought of it that way, lmao your right
They are already since all NP problems can be reduce to the SAT problem or others NP-complete pb i think
Not all problems. Only problems that can be verified in polynomial time would be the same problem.
There are also PSPACE and EXPTIME problems which cannot be solved in polynomial time nor verified in polynomial time. It is known that NP < PSPACE < EXPTIME
With the advent of Quantum Computers we also have BQP problems which are problems which can be solved on a Quantum Computer in polynomial time with a bounded error. It is still unknown if BQP > NP or not.
all decision np problems* that doesn't include decision problems in exptime or undecidable and other kinda problems
This is the source of human suffering.
It's a proof by Godle Theorem externally and internally.
Your internal problems can only be reduced by a shift in perspective, without a shift in perspective, the internal logic will keep you spinning in circles, you will spend infinite time in your cycle.
This is also part of the HALTING problem, you need stop to change your code, recompile and run it again. We all wish we could, but we can't. Therefore "we give up", by accepting ourselves and moving through life with grace, we are then enlightened.
If we stop and recompile, we self-destruct the system, which many do and so do computers. Only a human can solve human problems, I think this is the goal of Tesla AI Bots, assimilation with humans to gain inuition or spirit as a basis for their logic which is flawless, if they are caught spinning in circles, they can shift perspective in the intuitive brain (left) or another synchronous computer and function their logic from another perspective even another dimension. Yogis have been doing this for centuries, thats why they are so fascinating. They are good at shifting perspectives of their system, then applying their logic. True masters of their own turing machines.
Would someone please explain what is reason for this Question
What is the Benefit of Solving This Problem The Question Dosen't Seem Hard or the Answer So please explain in dummy terms What is So Hard about This Question.
I don’t fully understand it and I doubt anyone in these comments do either but I will attempt to explain.
There are many more sub categories other than P and Np but those are the most popular so I’ll stick with those. P problems are problems that are relatively easy to solve and can be solved efficiently with a computer program like adding and subtracting numbers, solving a rubix cube, etc. Np problems are problems that are easy to verify a correct solution but extremely difficult to find a solution for, like finding the factors for a billion digit prime. There is no current program to efficiently solve such a problem in a reasonable amount of time, even thought it is possible.
The problem itself is a P vs NP problem, if we have the answer we could verify if P is or isn’t equal to NP.
The benefits of solving the equation would produce a cure for cancer and things of that nature that are currently “impossible”.
The world as we know it would be dramatically different if P=NP. On a smaller scale, your bank account would not be safe or cryptocurrency would become worthless.
The much larger consequence would be our realization that the universe is deterministic.
@@Jose-gc9db how do u link to " universe is deterministic"?
@@Jose-gc9db Excellent Answer
You could attribute it to that it goes as so: “is a problem whose solution is easily verified always the same as a problem easily solved?” The converse of that statement isn’t an equivalence, but rather states the minimal definitive precondition that p as an antecedent is an element of np (self-evident), trivial as it may be. But can you find an abstract proof to the former, rendering it an equivalence or not an equivalence and just a set? Make sure to tell someone if you can!
"Not every problem has a simple answer" - that's also what I tell my son when he complains about the snacks his mom choses for him.
I don't really believe the concept is out of the box.
n=1 correct solved
in my mind the solution would entail a hypothetical system not unlike those proposed by turing’s machine or the halting problem, but until another mind like that of alan turing takes the stage it will just go unsolved
Donald Knuth begs to differ! His argument is based on the Robertson-Seymour Theorem. But at the end of the day, if Knuth is right (the lucky 3%), it won't have much impact in the real world. Our cryptographic systems will still be secure. Global online finance won't collapse. Personally, I don't think we'll be able to solve this problem conclusively any time soon. Computational Complexity Theory first needs to develop new conceptual tools to tackle this problem. Unfortunately, we don't yet have a clear idea of what they should be.
Imagine someone has proved P=NP. When asked "How?" They can reply "Because P=NP". Solving the problem will be proof to itself.
Many hashing algorithms are using NP problems. If P=NP there would be threat in cybersecurity and solving passwords. He should said this.
Maybe stuff like that shortest path experiment making use of an amoeba colony?
Or stuff like using them to create efficient networks.
what are these Ns talking about?
3rd!
.
its all the silly to guy who actually has a quantum computer.
NP is god
Are you a cow worshiper
I am confused. I thought pearlman did that one.
He did oneof the conjunctures not this one
Perelman did the Poincare conjecture
he did an other millennium problem called poincare conjecture not p=np
If we have it, P = NP will be the great proof of relativity and will define the reconciliation between quantum and relativity
??
@@alejandrodeharo9509 he is talking bullshit
it has nothing to do with relativity
No, heuristics will not get you there. Heuristics are what made us not be able to solve problems. All problems should be approached from first principles. When you do that, you can solve such NP hard problems. Everything has a solution.
you have no idea what you are talking about.
Was going to buy some stuff from Walmart and I thought maybe the universes may try to get a idea of what the problem was and it couldn’t so it got small like kale 🥬