Tags: astatine

tech contradiction

I like halogens!

Extremely obscure reference follows:

Say that you have a communications channel. As long as its SNR is above a certain limit (I don't remember which), it's possible to trade off speed to make it as reliable as required (by using turbo or LDPC codes). Now, the channel in question requires biological "operators" on each end (to transmit and receive), which would seem to make the use of error correcting codes infeasible (just show me the man who can calculate them in his head); however, both parties have access to computers, and one could then do as follows:

[transmitter] -> [computer encodes] -> arbitrary communications channel -> [computer 2 decodes] -> [recipient]

That should work even if your channel is "messenger pigeons that are being devoured by nearby eagles" or something equally random, or if the error is systematic, say the channel has some sort of (usually helpful) automatic translation system built into it. (If the error is bijective and static, we can easily untangle it, but that's besides the point as well as very unlikely.)

Okay, that's plain communications. Now consider the case where you want to know if the transmitter is connected to a computer of the strength he claims it to be. Since the transmitter is the one claiming the access in question, he may lie. But if we submit a proper input and function to him so that generating the coresponding output will take a certain amount of time, we can figure out a bound on the strength of the computer by seeing how long time it takes before he answers correctly. (Because of ECC, we can make random error as improbable as required.) At no time do we need to trust the transmitter, since the facts speak for themselves; the only attack here is for the transmitter to hide a computer "up his sleeve" and defer computation to it instead of using the publically claimed channel, but then whatever mechanism he uses to give information to that computer constitutes a communication channel of its own. Thus, we can prove the existence of at least one computer of the strength claimed, but we cannot distinguish between them if there are more than one.

(Feasibly, a person who just found that P == NP could (empirically) prove this by solving knapsacks supplied by an external party -- in the case of factoring, he might charge intelligence agencies for the ability to factor arbitrary positive integers. Of course, such would be a very dangerous game, and beyond the obscure reference.)