Results 1 to 7 of 7

Math Help - P versues. NP

  1. #1
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10

    P versues. NP

    As I understand this is an open and unsolved problem in math. I just wanted to ask what is it? Keep it simple never learned this stuff. Also if you may explain what computational complexity theory is. I tried wiki but could not understand.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    The question is about decision problems. We are looking for algorithms which determine whether a binary string S has a certain property Q. By using the idea of encoding a number, graph, function or whatever onto a binary string, we can speak more generally of deciding whether some mathematical object has a certain property. For example, "does S represent a prime number", "does S represent a composite number", "does S encode a graph which is connected", "does S encode a graph which has a Hamiltonian cycle", "does S encode a boolean function which is ever true". So the decision problem associated to Q is that of deciding whether the input represents an object with property Q.

    An important point which I'll mention here. The algorithm is only required to give the answer Yes when the input string does indeed have the property. If the input does not the algorithm may or may not terminate (but if it does, it musgive the correct answer of course!).

    A property, or decision problem, Q is in the class P (polynomial) if there exists an algorithm A which detects that S has property Q and which runs in time n^c where n is the length of the input string and c is a fixed constant depending only on A (this is "polynomial time"). It's an exercise in graph theory to show that if we encode a graph on V vertices by its V-by-V adjacency matrix, and then write that out as a list of length n=V^2, it is possible to check that the graph is connected in V matrix multiplications, ie V^4 operations. So this property is in class P. More recently it was shown that deciding whether a number is prime is in class P.

    A property Q is in class NP (non-deterministic polynomial) is there is an algorithm which can determine that S has property Q given some auxiliary input (which you could think of as a certificate, or witness, of S having that property). The algorithm is not required to produce that certificate, merely to check it. It should then run in time n^C as before. So, for example, if Q is "S represents a composite number" then an algorithm that takes as its certificate a factor and checks that is does indeed divide the input, runs in polynomial time. Similarly, for "does S encode a graph which has a Hamiltonian cycle", where the certificate is the path itself.

    The question "does S encode a boolean function which is ever true" is in NP (the certificate being an assignment of values to the variables making it true". The property, SAT, is NP-complete. Every problem in NP can be encoded in terms of a Boolean formula and the certificate in terms of an assignment of values to the variables.

    The big problem is about the relation between the classes P and NP. Clearly every problem in P is automatically in NP (with a null certificate). Is P = NP? Since SAT is NP-complete, a polynomial time algorithm for solving SAT without a certificate (ie a polynomial time for finding rather than merely checking the solution) would be enough to show that P = NP.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by rgep
    The question is about decision problems.
    :
    :
    I think I would have pitched this at a slightly more elementary level
    myself .

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    I think I would have pitched this at a slightly more elementary level
    Feel free to do so ...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Thank you rgep (though not fully understood), why is it so important?

    Can P=NP be independent?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    There are some good resources at the Clay Mathematics Institute site.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by rgep
    Feel free to do so ...
    Roger Penrose already has in "The Emperor's New Mind", pages 181-187.

    It's a bit too long to reproduce here, but it is pitched at the right level
    for someone not familiar with the field.

    Or chapter 6 of David Harel's "Algorithmics"

    RonL
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum