Thread: t-shirt

Originally Posted by Aisthesis

It's also well-known (and provable) that there are true statements that aren't provable...

Indeed. It crossed my mind yesterday. And it's quite possible P != NP fits in Gödel's theroems. But we can't answer that yet either.

What troubles me, is that it seems there's no working hypothesis (as you put it) in P != NP. P != NP has become instead an unspoken behavioral axiom. Meaning, it's not a true axiom, but influences the behavior for future search. It has been reduced to "I believe in P != NP, because no one could yet prove P = NP" and this could have spelled to some "Trying to prove P = NP is a research dead end". It's no surprise that the pool (pdf file) linked to at the Wikipedia article reveals much of the work has been done on trying to prove P != NP. There's already something seriously wrong.

So all this is in fact my stab at those researchers whose lack of evidence on P = NP have them behaving like P != NP is the solution, halting or moving research or even already advocating the solution on faith, which makes me doubt their value as scientists. It's more distressing when you think the huge revolution and scientific advance it could be if someone proved P = NP. The prize is too great to be ignored. Whereas the future seems bleak if P != NP.

But P = NP can indeed be a wild goose chase, while P != NP seems a lot harder to prove (or even plain impossible). So it may be many years, hundreds of years, thousands before we reach a solution, if we ever do. A t-shirt is a funny and I certainly am not having a go at it, or you for putting P != NP on it. But I felt I had to comment.

Mario, while I still don't entirely understand why even the dogmatic belief that P != NP would suggest that P == NP,

When I move to "dogmatic belief", I steer away from Science. In that brave old world of belief and faith, the rules are played differently. In here, I proved P != NP through my belief in the form of a canon of faith. This canon serves both to prove the solution and to validate it. I equaled the solution and its validation.

Back on the scientific world, this makes no sense. But in the reality I emerged myself in, I actually unknowingly made a strong case for P = NP and didn't prove P != NP. It's not possible to prove P != NP in this reality of faith I got myself into. Every effort will put me closer to P = NP.

I struggling with words at this point. I don't know what else I can say. I'm not proposing the belief finds its echo in scientific reality. I'm saying that in the pseudo-reality imposed by faith, trying to prove P != NP will in fact have you unwillingly prove P = NP. In that pseudo-reality. Not in the scientific reality.

Originally Posted by Mario F.

Whereas the future seems bleak if P != NP.

You don't really mean that.

Originally Posted by MK27

You don't really mean that.

It worries me somewhat.

P != NP seems to imply as our knowledge progresses and we reach more complex problems, we will have an increasing difficult in finding solutions. From the perspective of computer programs alone, we may reach a threashold in which we simply cannot compute the solution. There's no guarantee we can evolve our computing power at the same pace of our discoveries and subsequent new challenges. It seems to imply knowledge will evolve progressively slower.

But it does make sense, I guess. Knowledge being dragged down to the speed of our technological advances. It surely is what we have been experiencing so far. But I would like to dream, as a species we are still in the infancy of our intellectual abilities. Our brain is today essentially the same brain that had us living in caves and formulating the first supernatural explanations for the thunder and the stars. It's possible that P = NP. We just can't reach it yet. We are still too dumb.

Originally Posted by Mario F.

P != NP seems to imply as our knowledge progresses and we reach more complex problems, we will have an increasing difficult in finding solutions. From the perspective of computer programs alone, we may reach a threashold in which we simply cannot compute the solution. There's no guarantee we can evolve our computing power at the same pace of our discoveries and subsequent new challenges.

We're already there. There is obviously a set of problems which can be solved by a computer and a set which cannot. If all math problems are in the first category (I presume they are), you are now into a standard philosophical debate (can all human problems and questions be reduced to math or a binary logic?).

If a problem can be proven to be machine solvable, we could save ourselves a lot of trouble (never mind the fact that this is politically infeasible in many cases). So I do agree is a waste of time to try and prove that it is not possible and therefore you should give up on it.

However, pragmatically and personally speaking I'm inclined to believe that trying to prove it is possible is also a waste of time. I think the possibility of machine sentience and consciousness lies between here and there and is probably a faster route to there.

It seems to imply knowledge will evolve progressively slower.

If knowledge is a finite realm that is not undesirable. Eventually it should stop altogether, once you know everything

It also hinges on the belief that P vs NP is "the most important problem in the field [of computing science]" as wikipedia claims "many theoretical computer scientists" believe.

Which that is not a provable hypothesis, and while I can kind of see why some people might believe it, I don't (of course, I am not much of a "theoretical computer scientist"). Who cares if P != NP? I do not think it has the drastic consequences Mario attaches to it.

Originally Posted by Yarin

Mario, it seems that you're unwilling to accept that P != NP because it conflicts with your beliefs and desire for humanity's future. (Ironically, what you where accusing P != NP advocates of doing.)

Well no I'm not. But I can understand you took the easy conclusion.

Originally Posted by Mario F.

What troubles me, is that it seems there's no working hypothesis (as you put it) in P != NP. P != NP has become instead an unspoken behavioral axiom. Meaning, it's not a true axiom, but influences the behavior for future search. It has been reduced to "I believe in P != NP, because no one could yet prove P = NP" and this could have spelled to some "Trying to prove P = NP is a research dead end". It's no surprise that the pool (pdf file) linked to at the Wikipedia article reveals much of the work has been done on trying to prove P != NP. There's already something seriously wrong.

I think that you have missed the pragmatism of an approach where one regards P != NP being more probable based on the current evidence, and thus research proceeds as if it is proven that P != NP. Suppose that later it is shown that P = NP, and an algorithm is supplied. The research on handling the presumed intractable nature of problems in NP might not be rendered obsolete, since the new algorithm still might not be efficient enough in practice.

For example, consider that it has been proven that primality testing is in P. Yet, probabilistic algorithms such as Rabin-Miller are still used in practice instead of AKS, because they are more efficient, with the margin of error regarded as tolerable.

On the other hand, proceeding as if P = NP might be overly optimistic: your research would not have any immediate benefits, and if it is later shown that P != NP, your research would then become obsolete.

Originally Posted by EVOEx

Let me first say that the only proof of P being not equal to NP is the absence of a proof that P is equal to NP.

That sounds like a converse error. P != NP implies the absence of a proof that P = NP, but the absence of a proof that P = NP does not imply that P != NP.

Originally Posted by laserlight

For example, consider that it has been proven that primality testing is in P. Yet, probabilistic algorithms such as Rabin-Miller are still used in practice instead of AKS, because they are more efficient, with the margin of error regarded as tolerable.

On the other hand, proceeding as if P = NP might be overly optimistic: your research would not have any immediate benefits, and if it is later shown that P != NP, your research would then become obsolete.

This is why I said* it is a little silly to regard P vs NP as "the most important question in computer science" -- it is hard to see how proof that P = NP would have any practical consequences at all.

* I did not know that about primality testing but a polynomial time solution is not by definition a better solution than an exponential time one (even tho it most likely is).

I think that you have missed the pragmatism of an approach where one regards P != NP being more probable based on the current evidence, and thus research proceeds as if it is proven that P != NP. Suppose that later it is shown that P = NP, and an algorithm is supplied. The research on handling the presumed intractable nature of problems in NP might not be rendered obsolete, since the new algorithm still might not be efficient enough in practice.

For example, consider that it has been proven that primality testing is in P. Yet, probabilistic algorithms such as Rabin-Miller are still used in practice instead of AKS, because they are more efficient, with the margin of error regarded as tolerable.

It's a good argument you have there Laserlight. Didn't think about it that way. Thanks for that.

Originally Posted by MK27

This is why I said* it is a little silly to regard P vs NP as "the most important question in computer science" -- it is hard to see how proof that P = NP would have any practical consequences at all.

The immediate benefit of the discovery of an answer is not tied to direct scientific or technological benefits. A proven P = NP or P != NP would help our scientists guide their research. The material benefits could probably still take some time. But there's no denying P = NP would bring the most benefits.

I think the article at Wikipedia does a good job laying out the potential benefits of each answer.

...

But even ignoring the actual benefits that could be drawn from finding the answer, I would still question your argument.

Laserlight argument that a NP solution may be preferable to a P solution is not meant, I'm sure, to be generalized to the whole set of NP problems. Some of these could benefit from their P counterpart. And many of the NP problems are fundamental problems in their fields.

Meanwhile, once in P a solution is more permeable to technological advances. Admitting further progresses in computer technology, an inefficient P solution today, may become an efficient one tomorow.

Originally Posted by Mario F.

I think the article at Wikipedia does a good job laying out the potential benefits of each answer.

IMO also.

A proof of P = NP could have stunning practical consequences, if the proof leads to efficient methods for solving some of the important problems in NP.

Which might be to say, there are important practical problems to solve, and this rather ridiculous possibility could contribute in some measure. And I have nothing against pure academia at all, I'd love to be working there. But I dunno if this would be my first choice of assignments.

In a 2002 poll of 100 researchers 61 believed the answer to be no, 9 believed the answer is yes, and 22 were unsure; 8 believed the question may be independent of the currently accepted axioms and so impossible to prove or disprove.

I wonder how many of those in the "no" and "unsure" categories simply had a problem with whatever language "independent of the currently accepted axioms and so impossible to prove or disprove" was couched in for the survey, because despite my ignorance of math it does look that way to me (impossible to prove or disprove). And kind of like 91% of researchers might almost agree, but some noticeable measure of those concede there are fundamental inconsistencies at play.

I am not claiming, by the way, that this is something I think limited about the nature of math or computer science, but (axiomatic) it is something about the state of our empirical limitations*. Meaning working on such a problem within the current framework will only prove fruitless, like climbing the extreme end of an exponential curve. It will simply cost more and more time and resources to accomplish less and less.

It could be that the way out of such a framework lies in the field of P vs NP, I suppose.

*which is why I think the way out lies not in the field of P vs NP but in expanding our empirical limitations.