Re: ℙ≠ℕℙ proof

On Sun, 2024-05-19 at 04:21 +0200, immibis wrote:

On 18/05/24 14:18, wij wrote:

On Sat, 2024-05-18 at 12:36 +0200, immibis wrote:

On 18/05/24 12:10, wij wrote:

If no more information of the
key is given, the computation of key_exist(..) can only be done by
visiting each one of O(2^|ctext|) possibilies of the key.

 
prove it

 
You cut off the relevant phrase. "Every key has to be visited", though phrased differently

 
prove that every key has to be visited

So, if given the decipher machine, ciphertext and the plaintext (formally,
f:C×K->P, C,K,P⊆ℕ) you have an idea of any chance figuring out whether or not a
key∈K exist better than trying each possibility of the key from the given
condition. What is it? What should be supplemented in the proof?