<p>Kolmogorov complexity might fall into this category.</p>

<p>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.</p>

CC BY-SA 3.0
2012-01-12T23:51:51.777Z
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.)
Kaveh
CC BY-SA 3.0
2012-01-13T03:01:04.243Z
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.
David Harris
CC BY-SA 3.0
2012-01-12T21:14:39.687Z
2012-01-12T21:14:39.687Z
David Harris
<p>In some sense, this is what the theory of parametricity is all about. </p>

<p>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. </p>

<p>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. </p>

CC BY-SA 3.0
2012-01-13T23:13:04.183Z
The data is accessed via an appropriate oracle, but that does not necessarily imply that it is uncomputable to access it directly
David Harris
CC BY-SA 3.0
2012-01-14T10:27:09.680Z
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.
Neel Krishnaswami
CC BY-SA 3.0
2012-01-13T14:25:43.743Z
2012-01-13T14:25:43.743Z
Neel Krishnaswami
<p>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).</p>

<p>My question is : </p>

<blockquote>
  <p>do we have similar results in computability theory? Are there interesting positive constructions using negative impossibility results? </p>
</blockquote>

<p>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?</p>

CC BY-SA 3.0
2012-01-12T21:11:36.557Z
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).
David Harris
CC BY-SA 3.0
2012-01-12T21:11:53.840Z
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.
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-12T23:44:12.833Z
@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.
Kaveh
CC BY-SA 3.0
2012-01-12T23:47:13.280Z
@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?
Kaveh
CC BY-SA 3.0
2012-01-13T02:34:11.650Z
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".
Ludovic Patey
<cc.complexity-theory><cr.crypto-security><computability>
Using negative results to prove positive results in computability theory
Kaveh
# Using negative results to prove positive results in computability theory

(Asked by: username_0 on 2012-01-12)

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?

**Tags:** cc.complexity-theory, cr.crypto-security, computability

> **Comments:**
> **username_1**: 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).  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_0**: @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?  
> **username_3**: 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".  

---

## 2 answers

### Answer by username_4 on 2012-01-13. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_1**: The data is accessed via an appropriate oracle, but that does not necessarily imply that it is uncomputable to access it directly  
> **username_4**: 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.  

---

### Answer by username_1 on 2012-01-12. Score: 7

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.

> **Comments:**
> **username_0**: 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.)  
> **username_1**: 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.  

---

