Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #136145

Re: P!=NP proof (revised)

Show all headers | View raw

wij <wyniijj5@gmail.com> writes:

> The following is a snipet of the revised proof
> https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
>
> I think the idea of the proof should be valid and easy to understand. The rest
> technical apart should be straightforward (could take pages or dozens of pages,
> so ignored). But, anyway, something like the C/C++ description is still needed.
> Can you find any defects?
>
> --------
> ℕℙ::= {q| q is a decision problem that a computer solves in O(2^|q|) steps using
>        the following fnp algorithm template. q contains a verification dataset
>        C, card(C)∈O(2^|q|), and a Ptime verification function v:C->{true,false}.
>        If ∃c,v(c)=true, then the answer to problem q is true; otherwise, it is
>        false.}

This is not the set everyone else calls NP.

>     // begin_certificate is a Ptime function that retrieves the first
>     // Certificate element from the problem statement q. If this element does
>     // not exist, it returns a unique and virtual EndC element.
>     Certificate begin_certificate(Problem q);
>
>     // end_certificate is a Ptime function that retrieves the element EndC from
>     // the problem statement q.
>     Certificate end_certificate(Problem q);
>
>     // next_certificate is a Ptime function that retrieves the next element of
>     // c from the problem statement q. If this element does not exist, return
>     // the EndC element.
>     Certificate next_certificate(Problem q, Certificate c);
>
>     // v is a Ptime function. v(c)==true if c is the element expected by the
>     // problem.
>     bool v(Certificate c);
>
>     bool fnp(Problem q) {
>       Certificate c, begin, end;   // Declare the verification data variable
>       begin= begin_certificate(q); // begin is the first verification data
>       end= end_certificate(q);     // end is the false data EndC used to
>                                    // indicate the end.
>       for(c = begin; c != end;
>           c = next_certificate(q, c)) { // At most O(2^|q|) steps.
>                                         // next_certificate(c) is the Ptime
>                                         // function to get the next
>                                         // verification data of c
>           if(v(c) == true) return true; // v: C->{true, false} is the polynomial
>                                         // time verification function.
>       }
>       return false;
>     }
>
>     Since a continuous O(P) number of Ptime functions (or instructions) can be
>     combined into a single Ptime function, if the complexity of each function is
>     Ptime, and the smallest unit of complexity is also Ptime, then it's roughly
>     the same. Any Ptime function can be added, deleted, merged, or split in the
>     algorithm without affecting the algorithm's complexity. Perhaps in the end,
>     only the number of decision branches needs to be considered.
>
>     [Note] This definition of ℕℙ is equivalent to the traditional
>     Turing machine definition of ℕℙ. The proof of equivalence is plain
>     and lengthy, and not very important to most people, so it is
>     omitted.

I'd like to see that proof since I don't believe the note is correct.

>     [Note] According to the Church-Turing conjecture, no formal language can
>            surpass the expressive power of a Turing machine (or algorithm) (i.e.
>            the decisive operational process from part to whole). C language can
>            be regarded as a high-level language for Turing machines, and as a
>            formal language for knowledge or proof.

The actual definitions of P and NP are based on Turing machines (and any
provably equivalent models of computation) so the Church-Turing thesis
is irrelevant.

> Problem Q::= Given plaintext a, ciphertext b, decoder d, and key length klen.
>     The key is a Ptime program. Problem Q determines whether there exists a
>     key c such that d(b,c)=a.
>
>     Problem Q can be computed using the following C/C++ pseudo code as fnp by
>     definition; therefore, Q∈ℕℙ.
>     Plaintext a, ciphertext b, decoder d, and the length of key klen are all
>     obtained from q:
>
>     bool f(Problem q) {
>       int MaxKey= ...                  // klen=maximum value of key (O(2^klen))
>       for(int c=1; c<=MaxKey; ++i) {
>         if(equ(d(b,c),a)) return true; // Polynomial-time verification
>                                        // (If c is not a valid program, then d
>                                        // returns a value such that equ test
>                                        // result is false)
>       }
>       return false;
>     }
>
>     Since the key is a freely written program, Each decription algorithm (key)
>     is essentially independent, and the given problem q may contain no
>     information about the algorithm's logic (knowledge of one key cannot be
>     used to deduce information about another).
>     Therefore, at least O(2^|klen|) possible key values must be tested one by
>     one. Thus, the complexity of problem q is O(2^N).

This is the classic "I can't believe there's other way" argument.  It's
not a proof at all.

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

P!=NP proof (revised) wij <wyniijj5@gmail.com> - 2025-11-19 15:21 +0800
  Re: P!=NP proof (revised) Ben Bacarisse <ben@bsb.me.uk> - 2025-11-20 00:06 +0000
  Re: P!=NP proof (revised) wij <wyniijj5@gmail.com> - 2025-11-28 11:43 +0800
    Re: P!=NP proof (revised) wij <wyniijj5@gmail.com> - 2025-12-11 23:23 +0800
      Re: P!=NP proof (revised) wij <wyniijj5@gmail.com> - 2025-12-14 17:26 +0800

csiph-web