4 ms·
That video helped a lot, but I'm still struggling to understand what the N=NP question means and how to prove it. I think that all problems with a set definiti
by z3t4 11y ago
That video helped a lot, but I'm still struggling to understand what the N=NP question means and how to prove it.
I think that all problems with a set definition for "solved" is solvable as in "P".
For example, the rubik's cube is solved if all sides have a solid color. And is thus a "P".
- Ar-Curunir 11y agoNP = Set of problems for which candidate solutions can be checked for correctness in polynomial time in the length of the input. P = Set of problems for which we can find a solution in polynomial time in the length of the input. Clearly, P \subseteq NP. Proving P = NP would require proving NP \subseteq P, something which most people would believe to be a) highly unlikely b) difficult.
- z3t4 11y agoSo basically I have to find a problem that categories as P but not NP!? Kinda like the Planck constant in quantum theory. f(2) = 4, f(3) = ? /brainstorming
- Ar-Curunir 11y agoWell no, every problem in P is in NP trivially. To prove P = NP, you would have to prove that one of the many NP-Complete problems has a polytime algorithm. Well that's not the only way to prove P = NP, but that's one approach.
- nsnick 11y agoTo prove that P does not equal NP you would have to prove that a problem thought to be NP Complete was in fact NP Intermediate. That is, the problem meets the conditions of NP, but NP Complete problems cannot be reduced to it.
- Ar-Curunir 11y agoNo, not really. There are many NP-Complete problems, and there are many NP problems that are thought to be neither NPC nor in P. In fact, if P != NP, there are infinitely many such problems. So proving P != NP could proceed by finding some problem in NP that is not also in P.
- nsnick 11y agoWhich problem do you think is NP but is not NP Complete?
- Ar-Curunir 11y agoSee: https://en.wikipedia.org/wiki/NP-intermediate https://en.wikipedia.org/wiki/NP-intermediate
- nsnick 11y agoGreat link I particularly like the part that says, "P = NP if and only if NPI is empty." seems to indicate that if there are any NP Intermediate problems P would be proven not to equal NP.
- mnarayan01 11y agoThat's pretty far from your original statement. Which isn't to say that's not what you _meant_ in your original statement; just that it's not how I (and minimally the GP) read it.
- deleted 11y ago[deleted]
- justifier 11y agowhat we are concerned with here are two things, that becomes easier to explain as three things: * the problem's class * the algorithm.. or proof * the size of the input * the problem's class: each problem has a corresponding class(i) determined by a universal set of rules based on current solving algorithms and how they react to different input in a beautiful and approachable paper by richard karp titled: reducibility among combinatorial problems(ii); karp showed that the hardest problems, that seem unable to be solved in polynomial or subpolynomial time, called NP-Hard, are basically all the same problem viewed from different perspectives karp develops reducibility, a process used to show that one can reduce any of his 21 chosen problems into any of the others through a specific tree of transformations he calls reductions this set of problems that form the tree of reductions is called NP-Complete i say it is approachable because this paper develops reducibility and as such lacks any assumption about the reader's previous knowledge . * the algorithm: check out this chart(iii) that lists some time complexities, you will see polynomial,P, time about mid way through polynomial time is 2^O(log n) or poly(n), that 'O()' syntax is something called big O, which is analogous to a sort of algorithmic measurement unit(iv) derived from number of necessary operations in relation to the size of the input all algorithms before the polynomial time listing are sub polynomial time for any inputs and as such are classified as P . * the size of the input: lots of np problems have algorithm solutions that can solve specific inputs in polynomial time sometimes those inputs are small, or follow a specific pattern, but a general purpose algorithm, or a collection of specific algorithms that can be proved to cover all possible inputs, that runs in a reduced(v) complexity of polynomial or sub polynomial time is necessary to be classified P one way to prove P=NP is to take one of karp's problems and develop an algorithm that satisfies the above stated requirements once developed karp's reductions can be used on the algorithm to show that all NP-Complete problems are in P as well, therefore P=NP . (i) http://en.wikipedia.org/wiki/Complexity_class http://en.wikipedia.org/wiki/Complexity_class (ii) http://www.cs.berkeley.edu/~luca/cs172/karp.pdf http://www.cs.berkeley.edu/~luca/cs172/karp.pdf (iii) http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities http://en.wikipedia.org/wiki/Time_complexity#Table_of_common... (iv) http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation (v) https://justin.abrah.ms/computer-science/big-o-notation-explained.html https://justin.abrah.ms/computer-science/big-o-notation-expl...
- Gibbon1 11y agoMy simplistic take away is it's an answer to this question about algorithms. For a problem you can have a number of different algorithms to solve the problem. And a number of algorithms to check the solution to a problem. This is a point that is skipped over and trips lay people up because in school people are usually taught _the algorithm_ for solving a problem. But there are all sorts of ways to skin the cat mathematically. Some of these algorithms are great and some are 'bad' Polynomial time algorithms are good. Ones that blow up exponentially are bad. The question is, if you find a good polynomial time checking algorithm for a problem, does that mean there are polynomial time solving algorithms for that problem? Or not.
- Gibbon1 11y agoJust wanted to add, out of my butt I think the point not explicitly stated is, if you can prove P=NP then I think it means that you can also mechanically transform polynomial checking algorithms into polynomial time solving algorithms.