I came from an electronics background when I first started reading algorithms my head was spinning. And I am sure a lot of other novices/laymen from the same problem.
The reason I have seen over the years is simple. Expressing the problems in terms of mathematical equations. Mathematical equations some how denote a way of modifying elements through equations. They tend to build on existing established principles of maths. There fore in order to understand what the other person is saying a person must get into a high learning curve.
When I first read about P Vs NP problem, I really wasn't able to co relate it to anything in the real world. Later on as I read more on puzzles like The Bin packing problem, or the traveling salesman problems. Things began to make sense.
The way to explain people about such things is to give them problems defined in simple English. And then allow them to build their own way of representing objects and elements, and the way they choose to modify them. Like this article does, However while explaining to people start from very small input sizes. Help them work out outputs for large input sizes.
Given the problem at hand, explain them why such large computation time doesn't make sense in the physical world.
Representing the problem in pure math will never help the guy next to your home. Giving him a day to day use case, will force him to think.
So here we go, what all common every day use cases fit into the P Vs NP problem? If we can create such a list, a lot more laymen can think and build on those problems easily!
doubtful. a programmer could spend an entire career in industry and never run into an np complete problem he needed to solve.
i added more examples to the article, and made them as simple and practical sounding as possible, but to be honest my primary interest in the problem is mostly from a theoretical perspective. to me, the idea that P != NP implies a host of bizarre conclusions that seem incredibly unlikely to me. i am so convinced of this that i had it emblazoned my license plate:
to be honest, mostly it's because i enjoy disagreeing with people who are convinced of things they don't have a full understanding of. if you are decently educated, you realize how much there is we don't know, and approach every unsolved puzzle with a combination of curiosity, confidence and humility. philosophy aside, here's my thinking:
LONG VERSION: Suppose P is an NP complete decision problem; for each instance, the answer is either 'yes' or 'no'. Let P have verifying function V. Let the language L be the set of all binary strings s that represent instances of P for which V(s) = 1, i.e. the set of all strings s that represent instances of P for which the answer is 'yes'. If L (the set of all instances of P for which the answer is 'yes') is finite, then you can easily answer all instances of the problem P in constant time by using a lookup table that stores all members of L (i.e. all finite languages are regular.)
So, consider the case when L is infinite. We know that V must be expressible in terms of a finite sequence of symbols. Suppose we have manged to express V using a total of C bits. The entropy of all C-bit binary sequences is bounded by a function of C alone; i.e. it is independent of the specific content of V, all that matters is how many bits are in some (it doesn't matter which) implementation of V. My primitive understanding of information theory tells me that if V has a finite amount of information, and L is uniquely determined by V, then L cannot possibly have MORE information than V; if you have V and enough time, you can compute all of L. This limits the possibilities of L, and suggest to me that there must be a way to find a (possibly complex and incomprehensible algorithm) for solving all instances of P, by 'compressing' L in just the right way. I admit that this is very hand-wavey; i just don't know enough information theory to pin everything down.
SHORT VERSION: if you can verify all solutions to a problem using a function expressible using a finite sequence of symbols, then the total information content of a sequence representing all solutions to the problem can't exceed the information content of the verifying algorithm.
if P != NP, this (to me) implies that a list of answers to a problem somehow has more information than an algorithm that can be used to generate that list of all answers. it seems to me that the algorithm could easily contain more information than the list, but not the other way around.
to put it another way, if you see a verifying function as a compression algorithm on the list of all solutions (because they contain the same amount of information), then P != NP implies that some infinite sequences (which represent np complete problems) are simultaneously so redundant that they can be compressed to a finite length, but at the same time are so complicated that you can't figure out an arbitrary element without doing a massive amount of computation. as i see it, some patterns can appear random unless you look at them from just the right perspective, and then the pattern emerges. because np-complete problems can be expressed with a finite amount of information, there has to be a pattern that we're not seeing yet.
The reason I have seen over the years is simple. Expressing the problems in terms of mathematical equations. Mathematical equations some how denote a way of modifying elements through equations. They tend to build on existing established principles of maths. There fore in order to understand what the other person is saying a person must get into a high learning curve.
When I first read about P Vs NP problem, I really wasn't able to co relate it to anything in the real world. Later on as I read more on puzzles like The Bin packing problem, or the traveling salesman problems. Things began to make sense.
The way to explain people about such things is to give them problems defined in simple English. And then allow them to build their own way of representing objects and elements, and the way they choose to modify them. Like this article does, However while explaining to people start from very small input sizes. Help them work out outputs for large input sizes.
Given the problem at hand, explain them why such large computation time doesn't make sense in the physical world.
Representing the problem in pure math will never help the guy next to your home. Giving him a day to day use case, will force him to think.
So here we go, what all common every day use cases fit into the P Vs NP problem? If we can create such a list, a lot more laymen can think and build on those problems easily!
Is there such a list lurking somewhere?