[rsofaer]

I didn't understand this sort of math at all until I spent some time in a formal Theory of Computation class studying first finite automata/regular languages, then PDA/CFL and other related topics. I don't think you can expect to understand the reasoning that led to the P=NP question without that kind of study. You must learn the math.

On the other hand, here's a short summary of P=NP itself:

There is a large group of problems called NP (Non-Deterministic Polynomial), which have been shown to be equivalent, in that a polynomial time algorithm for one could be used to construct polynomial time algorithms for all the others. These problems all have the property that a possible solution can be tested in polynomial time. Because NP is big, many of the problems within it are useful, and it isn't intuitively very far from problems which are soluble in polynomial time, a lot of work has been done on trying to either find polynomial time algorithms for NP, or show that no such algorithm could exist.

edit: As lacker mentions, one intuition about NP problems is "Problems for which you must check all the possible solutions and see which one is right."

[orionblastar]

What is polynomial time and Non-Deterministic Polynomial? Please explain these in simple terms.

[rsofaer]

NDP is what I said above, you can test a solution in polynomial time. You should get an algorithms textbook to read about time complexity of algorithms if the "Time Complexity" page on wikipedia doesn't make sense to you. I used Cormen's textbook in my algorithms class. This is important, you're going to have trouble if you don't really understand the asymptotic (as the data structure gets large) difference between, for example, searching a list and searching a tree.

[orionblastar]

From my limited understanding a list is a data structure that contains an ordered number of items. For example a linked list that has a pointer to the next item in the data structure that keeps the list in order. A tree data structure has sub-sets of linked nodes starting at a 'root' node, much like a tree.

How does time complexity fit into that?

[tptacek]

The list and the tree don't themselves have time complexity; operations on them do. Finding an element in a list takes O(n) time; in the worst case, you have to check every element of the list. Finding an element in a balanced binary tree takes O(log n) time: at each step, you halve the number nodes you need to check.

The balanced binary tree search operation is an example of something whose cost grows very slowly even as the size of the tree grows rapidly.

There are algorithms that are hard the same way the O(log n) tree is easy: they grow exponentially with the size of input, so very small changes in the input size can drastically increase their cost.

[orionblastar]

What is this "O"? This is what I am talking about, the Wikipedia article and even this thread throw out variables without defining what they are. "O" and "n" what are they, how do I calculate them? How do they work? That is why none of this makes any sense that I can understand.

[brudgers]

Seriously, what is "n" often used to signify in math? Stop thinking of reasons to complain and read for comprehension. Then you will be halfway through O(n).

Then if you write down what you think O signifies, you will be at least 3/4 to the answer instead of part way. Nobody can learn for you. Only you can put forth the effort required.

Cowboy up.

[tptacek]

Well, I tried. Good luck!