9
$\begingroup$

Many results in cryptography depend on impossibility results/conjectures in complexity theory. For example, public-key cryptography using RSA is believed to be possible because of the conjecture about infeasibility of the factoring (and the modular root finding problems).

My question is :

do we have similar results in computability theory? Are there interesting positive constructions using negative impossibility results?

E.g., does the undecidability of the halting problem allow us to perform tasks that we would not be able to do if the halting problem was decidable?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Two main uses of negativity results in complexity theory are (1) cryptography and (2) derandomization. Neither of these apply in the computability framework. Deciphering a computable cryptosystem is inevitably a computable task, and any function computable on a random Turing machine is also computable on a deterministic Turing machine (in a constructive way). $\endgroup$
    – David Harris
    Jan 12, 2012 at 21:11
  • 1
    $\begingroup$ this seems to be a question of wording. "public-key cryptography using RSA is possible" is just the glass half-full way of saying "cracking RSA in poly-time is impossible". I don't see how RSA is a positive construction... it is just a construction, and its security proof is a negative result about possible adversary algorithms. $\endgroup$
    – Artem Kaznatcheev ♦
    Jan 12, 2012 at 21:11
  • $\begingroup$ @Artem, the point here is that we are constructing a protocol that can be used and the condition that the protocol is useful is a negative result that there are no adversaries that can break it. Intuitively what I mean by a negative result is a theorem that says something cannot be done. By a positive result I mean a construction that allows carrying out some task (e.g. secure communication). A positive result may have a negative result inside it. I will think about expressing this more formally. $\endgroup$
    – Kaveh
    Jan 12, 2012 at 23:44
  • $\begingroup$ @David, yes, I am aware of these two. Do you know any other known use of the negative results for positive results in complexity theory/crypto? $\endgroup$
    – Kaveh
    Jan 12, 2012 at 23:47
  • 5
    $\begingroup$ I personaly also think it's a question of wording. For example, you can take Rice theorem, and say "for each antivirus, you can construct a virus not recognized". In every incompleteness theorem, you can transform it into "you can construct a counterexample". $\endgroup$
    – Ludovic Patey
    Jan 13, 2012 at 2:34

2 Answers 2

Reset to default
8
$\begingroup$

In some sense, this is what the theory of parametricity is all about.

Data abstraction is how we ensure that no client of a module can access the elements of a module except according to the interface exposed by the module. We rely on this to ensure that the internal invariants of data structures cannot be broken by the clients of a module -- eg, if you access a balanced tree only via the published interface, then it follows that the tree will always be balanced.

So we use a negative property -- that no possible client can break the abstraction boundary -- to deduce a positive one -- that the data representation invariant always holds.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The data is accessed via an appropriate oracle, but that does not necessarily imply that it is uncomputable to access it directly $\endgroup$
    – David Harris
    Jan 13, 2012 at 23:13
  • 2
    $\begingroup$ Data abstraction is essentially a definability result: it says that no program in the programming language can break abstraction boundaries. If you use an extra-linguistic mechanism (e.g., you fire up your debugger), you can of course see what private fields that hash table has. $\endgroup$
    – Neel Krishnaswami
    Jan 14, 2012 at 10:27
7
$\begingroup$

Kolmogorov complexity might fall into this category.

One can show that there are certain strings, which cannot be compressed by any Turing machine. These strings behave "generically" so you can study the random properties of certain information and computational tasks by studying the behavior with respect to a (non-random) incompressible string.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, someone else also suggested this in an offline discussion. (I am not completely convinced since we don't really use computationally random string to perform real world tasks, it has more of a existential flavor than building something, I should probably think a little bit more about what I exactly mean by a positive result. ps: my original motivation was to give undergrad students learning computability theory an example of usefulness of negative results in building things to perform real world tasks.) $\endgroup$
    – Kaveh
    Jan 12, 2012 at 23:51
  • $\begingroup$ While one does not (and cannot) construct incompressible strings in practice, it is very common to construct a string randomly. Then, with high probability, it will be incompressible. $\endgroup$
    – David Harris
    Jan 13, 2012 at 3:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.