Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Platonism, NP-complete

  1. Nov 9, 2009 #1
    The following in an argument for platonism:


    A problem X is a question that can be answered with either a yes, or no.

    "X is in P" is the same as saying X is in the class of questions with polynomial runtime algorithm.

    "NP" is the class of problems with B that takes two parameter, t, and s such that B( t, s)= true. The length |t| is less than, or equal to O( p( |s| )), where p is polynomial function.
    |x| stands for the length of the string, so |erew|=4. O is the upperbound runtime for |t|.
    s is in X. t is a prove/evidence of s in X. So, if t is evidence of s in X, then B( t, s) =true.

    Theorm 1: everything in P is in NP.
    Prove: exercise.

    Hard problems are np-complete problems. NP-complete are a special class of problems in NP such that every NP problem can be reduce to a NP-complete problem. That is to say, If X is any NP-complete problem, and Y is in NP, then we can encode/transform Y into X. Thus, A solution for an NP-complete X in a solution for all NP problem Y.

    Theorm 2( state without prove): If X is np complete, and Y in an NP such that we can encode/transform X to Y so that a solution of Y result in a solution of X, then Y is NP -complete.


    By the theorm 2, once a NP-complete problem is solved by an algorithm A, then all NP, NP-complete, and P can be solved by A. So we seem to have a class of problems( NP-complete) that are hard, and share the same complexity. This is by no mean a priori that all hard problems share the same complexity. Imagine a hierarchy of problems such that H_k is harder than H_(K-1), where K is an interger. This seems to comfirm platonism. That mathematical facts are objective, and mind independent. In our case, we have two choice. Choice 1: we have an infinite hierarchy of more, and more difficult problems with greater and greater complexity. In choice 2, we have different problem of the same complexity. To say that mathematical facts are not objective is to say a mathematical fact is not necessary. Suppose for a contradiction that this is the case. In the semantic of modal logic, then there would be a possible worlds w, and w* such that with out loss of generality choice 1 hold in W and choice 2 hold in W*, but this contradiction our intuitive that choice 2 hold in both W, and W*. Thus, mathematical facts must be necessary.

    for advanced readers, Necessity, and possibilities are metaphysical notions, white A priori are epistemic notion. Warning: Do not confuse the distinction difference.
    Last edited: Nov 9, 2009
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted