t-shirt

This is a discussion on t-shirt within the General Discussions forums, part of the Community Boards category; Originally Posted by Aisthesis It's also well-known (and provable) that there are true statements that aren't provable... Indeed. It crossed ...

  1. #46
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,488
    Quote Originally Posted by Aisthesis View Post
    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.
    Last edited by Mario F.; 04-03-2010 at 06:17 AM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  2. #47
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Mario F. View Post
    Whereas the future seems bleak if P != NP.
    You don't really mean that.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #48
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,488
    Quote Originally Posted by MK27 View Post
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  4. #49
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Mario F. View Post
    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
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #50
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,640
    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.)

    There is no proof one way or the other, I don't think anyone disagrees with that.
    However, our science at the point that it is at right now, says that P != NP; a mere sorting algorithm proves this.
    Sure, we may later evolve our science to allow us to prove that P = NP, but as it stands, nada suggests that that'll happen.
    When faced with the current evidence, there's reason to believe P != NP, and no reason to believe that P = NP.
    Why persist in the name of science? It's not on your side!
    A class that doesn't overload all operators just isn't finished yet. -- SmugCeePlusPlusWeenie
    A year spent in artificial intelligence is enough to make one believe in God. -- Alan J. Perlis

  6. #51
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #52
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,488
    Quote Originally Posted by Yarin View Post
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  8. #53
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    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. Many people have looked at NP problems and have never been able to find a solution in P. I consider it very likely that P != NP, although I'm not close minded to the opposite. But if P=NP, then it has to be extremely complex.

    Here are the consequences in Wikipedia:
    P versus NP problem - Wikipedia, the free encyclopedia
    But no, the future won't be "bleak" in any way.

    I am afraid of current encryption standards, though, should P=NP. It would mean it might be possible to crack current encryption algorithms (no, kryptkat, not one time pads) in a feasible time. But then again, who knows when quantum computers are advanced enough to factor numbers...

  9. #54
    Registered User
    Join Date
    May 2009
    Posts
    242
    Actually, now I'm seeing where Mario's coming from: It's becoming too much of a dogma rather than a research hypothesis.

    In the attempt to get a better grasp of what the problem actually is (and its explication is actually a bit more advanced than my current knowledge level in this area), I recently learned from a friend who has worked in that area that some problems in EXPTIME (the set of problems computable in exponential time) provably do not belong to P. Apparently the proof isn't that hard for those more advanced than I, but I don't know it.

    Yarin:
    our science at the point that it is at right now, says that P != NP; a mere sorting algorithm proves this.
    I think you're going a bit far with that statement. I at least wouldn't sign off on "science says ..." and certainly not on "proves."

    Because non-existence proofs can often be tricky (and the P v. NP question is essentially one, as I would assume the proof strategy, if and when we get one for inequality, will have to be showing that one of the NPC problems can't have an algorithm that runs in polynomial time), I'll be interested to see how one goes about devising an exptime problem that can't be computed in polynomial time.

  10. #55
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    Quote 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.

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #56
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    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).
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #57
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,488
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  13. #58
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,488
    Quote Originally Posted by MK27 View Post
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  14. #59
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Mario F. View Post
    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.
    Last edited by MK27; 04-03-2010 at 07:26 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  15. #60
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by laserlight View Post
    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.
    I didn't say it was a valid proof. Or, really, maybe I should not have used the word proof at all. It is the reason most scientists today believe that P != NP. With the words only proof I meant the only thing that points us to that direction. At least, so I believe, and I've read it a few times as well.
    It's like saying bigfoot exists. We don't have proof it doesn't. Most believe it doesn't because there has been little satisfying proof that it does exist, even though many have looked. It doesn't mean that it doesn't exist, just that it's very likely it doesn't, or can hide incredibly well.

    I agree with MK27 (for a change). I read about that research a while ago and I was kind of surprised by how many researchers still believed that P=NP. I don't. But when I read the "unprovable" part, it made me start thinking. Maybe it's not. I don't know. But I'd pick one of those. P!=NP or unprovable.
    Of course, one can guess based on the absence of evidence so far.

Page 4 of 5 FirstFirst 12345 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. I'm trying to count the frequency of the phrase "ing"
    By thefreeman1159 in forum C Programming
    Replies: 14
    Last Post: 09-23-2008, 11:58 AM
  2. Calling functions help
    By ForlornOdium in forum C++ Programming
    Replies: 14
    Last Post: 09-29-2003, 08:40 PM
  3. Clean Jokes
    By stevey in forum A Brief History of Cprogramming.com
    Replies: 35
    Last Post: 04-27-2002, 07:13 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21