Re: *Quantum Computing* expert Bill Munro

From: briggs@encompasserve.org
Date: 04/08/03 

From: briggs@encompasserve.org
Date: 8 Apr 2003 13:13:11 -0500

In article <3E930C69.8551D9A9@earthlink.net>, Benjamin Goldberg <goldbb2@earthlink.net> writes:
> Mok-Kong Shen wrote:
>>
>> jsavard@ecn.ab.ca wrote:
>> >
>> [snip]
>> > ..... Thus, while the quantum computer is a
>> > sufficiently disquieting development that one would want to use
>> > symmetric-key ciphers far more elaborate than are felt necessary
>> > today, it doesn't seem that problem is insuperable.
>> [snip]
>>
>> Very dumb question: If quantum computer ever breaks
>> any public key scheme, does it mean that P != NP is
>> refuted, or is there no such connection? Thanks.
>
> The class of NP problems are those which can be solved in polynomial
> time on a non-deterministic turing machine, but which, in worst case,
> with the best currently known algorithms, take superpolynomial time on a
> deterministic turing machine.

That seems to describe "NP complete" problems.

The "NP" set of problem classes is very simply those problem classes
which can be solved in polynomial time on a nondeterministic TM.
(Handwaving past the several pages of definitions that get us to the
point where we can formally say what it means for a problem class to
be solveable by a TM in polynomial time).

The "P" set of problem classes is very simply those problem classes
which can be solved in polynomial time on a deterministic TM.

The "NP complete" set of problem classes is a particular set of
problem classes that are known to be in "NP" and are known to
all be equivalent to one another. So if any are in "P", all are
in "P" and if any are not in "P", all are not in "P".

Clearly, P is a subet of NP. Whether P=NP is an open question.
Whether "NP complete" is a subset of P is an open question.

> If P == NP, then there exists some algorithm, which, on a deterministic
> turing machine, solves one of those problems in polynomial time.

True, but not what you meant to say.

        John Briggs

Loading