1. Forum
  2. Usenet
  3. SCI.MATH

  • Proof of P and NP

    From Suresh Devanathan@21:1/5 to All on Fri May 23 19:43:38 2025
    Suppose you are trying to solve a Boolean satisfiability problem C[x]. Now convert the problem into probabilistic domain.

    For probability vector x
    C[x] = p
    = p + 0*K*(B - p)
    = lim K->infinity p + 1/K*K(B- p)
    = B


    For friend
    in case a satisfiability, B = 1
    in case untestable, assume x_n= 0.5, B = 0

    For enemy,
    in case a satisfiability, B = 0
    in case untestable, assume x_n = 0.5, B = 1


    since by cook's thesis, even in 1 problem in NP proven to be P , every
    problem proven P. If
    reverse result is always true of enemy, the number of permutation is at
    least as great as 2^N
    where N is number of inputs, showing problem is be NP.

    complete proof




    -suresh

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Ben Bacarisse@21:1/5 to Suresh Devanathan on Sat May 24 01:15:22 2025
    Suresh Devanathan <[email protected]> writes:

    Suppose you are trying to solve a Boolean satisfiability problem C[x]. Now convert the problem into probabilistic domain.

    For probability vector x
    C[x] = p
    = p + 0*K*(B - p)
    = lim K->infinity p + 1/K*K(B- p)
    = B


    For friend
    in case a satisfiability, B = 1
    in case untestable, assume x_n= 0.5, B = 0

    For enemy,
    in case a satisfiability, B = 0
    in case untestable, assume x_n = 0.5, B = 1


    since by cook's thesis, even in 1 problem in NP proven to be P , every problem proven P.

    Not right. If a problem proven to be NP-complete is shown to be in P,
    then P = NP.

    If
    reverse result is always true of enemy, the number of permutation is at
    least as great as 2^N
    where N is number of inputs, showing problem is be NP.

    The problem must be NP-complete, not just in NP.

    complete proof

    Not yet.

    --
    Ben.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)