Re: Paper - impossible to prove P=?NP

From: Aatu Koskensilta (aatu.koskensilta_at_xortec.fi)
Date: 09/16/03 

Date: Tue, 16 Sep 2003 12:19:41 +0300

Bartosz Zoltak wrote:
> Authors of a paper at http://eprint.iacr.org (report 2003/187) say
>
> "(...) to prove P!=NP (by any technique and any reasonable theory) requires
> super-polynomial-time computational power"
>
> and
>
> "Even if P!=NP is true and there exists a (finite-size) meta proof of an
> asymptotic proof of this statement (in super-polynomial time), such a proof
> would be too long or too complicated for our humane being to create"
>
> If they are right, I look to have no point in trying to find someone who
> would be willing to find a proof that the VMPC function is one-way?
>
> Any ideas on this paper?

While I know next to nothing about cryptography, I do know something
about mathematical logic, and it seems to me that the claims in the
paper are somewhat exaggerated. For example, in the summary they offer
the following formulation of one of their results

  Let T be a consistent extension of PA. Then no polynomial time
  Turing machine can prove P != NP from T.

This is clearly wrong. Consider the theory PA + P != NP (and assume it's
consistent). Then a Turing machine which simply produces the statement
"P != NP" for any input is surely a counter example, since its running
time depends only on the complexity (length) of the statement "P != NP".
Later on in the paper they make various restrictions on the extensions
of PA they consider. This is necessary, since otherwise the results
would be incorrect, but it weakens the main argument considerably.

Also, there is an interesting theorem due to Gödel concerning the
lengths of proofs. It's known that if we add to any theory T a statement
expressing consistency of T, then the proofs of an infinitely many
statements are shortened by an amount not bounded by any recursive
function. This also occurs when one adds higher order constructs to the
theory, allowing quantification over sets, functions and relations of
elements of the domain. I would be highly surprised if someone could
come up with a natural fixed question - fixed so that we can avoid
questions referring to the particular system itself, some of which must
have arbitrarily long proofs - which provably would only have long
proofs in any sensible system.

In the paper the notion of asymptotic proof is defined basicly as follows

  Let P be a set of \Delta_1 formulas of form \psi(a_1, ..., a_k) where
  a_i are numerals, of some theory T extending PA, such that
  Q_1 x_1 ...Q_k x_k T |- \psi(x_1,..., x_k), where each Q_i is an
  unbounded quantifier.

  Then a set of Hilbert style proofs K is called an symptotic
  proof of P if Q_1 x_1 ... Q_k ( the proof of \psi(x_1, ..., x_k) is in
  P and the universal polynomial time Turing machine accepts the proof
  when simulating the polynomial time proof checking machine for T.

The claims of the paper would be substantiated if it could somehow be
shown that this concept of proof actually subsumes all humanly possible
forms of proof. I don't see any way to do this at our present stage of
understanding.

Disclaimer: I haven't yet waded trough the paper with full attention, so
it might be that I'm misunderstanding some of the results in the paper. 

-- 
Aatu Koskensilta (aatu.koskensilta@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
  - Ludwig Wittgenstein, Tractatus Logico-Philosophicus

Relevant Pages

  • Re: Paper - impossible to prove P=?NP
    ... "producing a proof" is not that of a Turing machine printing out the ... Assume now there's a polynomial time machine Proof, s.t. Prover ... Now the notion of asymptotic proof is defined in the part I quoted in my ... time machine Prover, s.t. ...
    (sci.crypt)
  • Please Help
    ... Instead of a deterministic Turing machine, ... The theoretical notion of "quick" used here is that of an algorithm ... in polynomial time, so this problem is in '''NP'''. ...
    (sci.math)
  • Re: An uncomputability conjecture, corrected version
    ... "Antti Ylikoski" kirjoitti ... which solves the problem and runs in a polynomial time. ... Turing machine that corresponds to R and solves the ... let be the set of input words to ...
    (comp.theory)
  • Re: Torkel Franzen on truth
    ... A Turing machine ... can indeed be a realized a physical machine (modulo size ... Human can conclude that PA is consistent, ...
    (sci.logic)
  • Re: paper claiming p=np and soap bubbles
    ... > macroscopic level can be modeled as a Turing machine, ... P are problems that take polynomial time on a deterministic ... A Turing machine can emulate nature. ... A deterministic Turing machine can emulate nature in polynomial ...
    (sci.math)