Posts

Showing posts with the label Conjecture

How can we all be right even when we believe incompatible things

Image
Reality is pretty complex, alright... Normally we expect reality to be far more complex than we can comprehend in a limited human mind. Each time we look to one object, many other objects go outside our perception field, even if the eye can still see them. And this is OK, because we have only a limited processing brain power for perceiving the reality. It's not only the limit of perceiving reality, there is also a limit in our capacity of "knowing" about reality. If we think about it, it is very intuitive: the physical mind is far smaller than the reality we want to know about. In order to know about reality, we need to have a model about reality stored inside our minds.

P=NP is undecidable (conjecture)

" P equals NP? "  is a million dollars unsolved problem . Introduction " P" is the class of problems where we have algorithms that solves the problem in polynomial time. " NP"  is the class of problems having solutions that can be proven in polynomial time once you "guess" the solution. This is analogous with the sorting problem: it's easier to check the correct sorting of a list than to actually sort a list. Of course, if you can fully solve the problem in polynomial time, you can also prove it in polynomial time, so P is included in NP. However, NP seems to contain some very hard problems that cannot be currently solved in polynomial time. It is believed that NP contains some problems that can never be possibly solved in P. I will not do a formal proof, more like an argument or a sketch. You might have more patience and skills to develop some of these ideas even if they might have flaws in the current form. You can take it a...