Y a-t-il des résultats contre-intuitifs en informatique théorique?

Certains paradoxes mathématiques et logiques pourraient probablement être automatiquement appliqués aux ordinateurs, mais y a-t-il des paradoxes découverts en informatique elle-même?

Par paradoxes, j'entends des résultats contre-intuitifs qui ressemblent à une contradiction.

Je trouve que le flux réseau est contre-temps polynomial intuitif. Il semble beaucoup plus difficile à première vue que de nombreux problèmes NP-Hard. Autrement dit, il existe de nombreux résultats dans CS où le temps d'exécution pour les résoudre est bien meilleur que ce que vous attendez.

$\mathsf{P} = \mathsf{NP}$$\mathsf{EXP} \not\subseteq \mathsf{P}/poly$$\mathsf{NEXP}$$\mathsf{ACC}$

SAT a un algorithme polynomial en temps uniquement si P = NP. Nous ne savons pas si P = NP. Cependant, je peux écrire un algorithme pour SAT qui est polynomial si P = NP est vrai. Je ne connais pas la référence correcte pour cela, mais la page wikipedia donne un tel algorithme et crédite Levin.

La calculabilité visse certainement la plupart des étudiants. Un bel exemple avec un taux de confusion élevé est le suivant:

$f(n) := \begin{cases}1, \quad \pi \text{ has } 0^n \text{ in its decimals} \\\\ 0, \quad else\end{cases}$

$f$

$f$

$IP = PSPACE$

Comme le disent Arora et Barak (p. 157) "Nous savons que l'interaction à elle seule ne nous donne pas de langues en dehors de NP. Nous soupçonnons également que la randomisation à elle seule n'ajoute pas de puissance significative au calcul. interaction fournir? "

Apparemment pas mal!

Comme l'a dit Philip, le théorème de Rice est un bon exemple: l'intuition avant d'étudier la calculabilité est qu'il doit sûrement y avoir quelque chose que nous pouvons calculer à propos des calculs. Il s'avère que nous ne pouvons calculer que quelque chose sur certains calculs.

Que diriez-vous des publications de Martin Escardo montrant qu'il existe des ensembles infinis qui peuvent être recherchés de manière exhaustive en temps fini? Voir le blog invité d'Escardo sur le blog d'Andrej Bauer, par exemple, sur "Programmes fonctionnels apparemment impossibles" .

Le théorème de récursion semble certainement contre-intuitif la première fois que vous le voyez. Essentiellement, il dit que lorsque vous décrivez une machine de Turing, vous pouvez supposer qu'elle a accès à sa propre description. En d'autres termes, je peux construire des machines de Turing comme:

TM M accepte n ssi n est un multiple du nombre de fois où "1" apparaît dans la représentation sous forme de chaîne de M.

TM N prend un nombre n et sort n copies de lui-même.

Notez que la "représentation de chaîne" ne fait pas référence ici à la description textuelle informelle, mais plutôt à un codage.

Prouver des résultats théoriques de l'information basés sur des hypothèses théoriques de complexité est un autre résultat contre-intuitif. Par exemple, Bellare et al. dans leur article The (True) Complexity of Statistical Zero Knowledge a prouvé de manière constructive que, dans l' hypothèse de log discret certifié , toute langue qui admet la connaissance zéro statistique du vérificateur honnête admet également la connaissance zéro statistique.

Le résultat était si étrange qu'il a surpris les auteurs. Ils ont souligné ce fait plusieurs fois; par exemple, dans l'introduction:

Étant donné que la connaissance zéro statistique est une notion indépendante du calcul, il est quelque peu étrange que des propriétés à ce sujet puissent être prouvées sous une hypothèse d'intractabilité informatique.

PS: Un résultat plus fort a ensuite été prouvé inconditionnellement par Okamoto ( sur les relations entre les preuves statistiques de connaissances nulles ).

Description de certains termes

Étant donné que le résultat ci-dessus comprend beaucoup de jargon cryptographique, j'essaie de définir de manière informelle chaque terme.

1. $p$$p-1$
2. Zéro connaissance : protocole qui ne fournit aucune connaissance aux parties limitées dans le temps polynomial.
3. Connaissances statistiques nulles: protocole qui ne fournit aucune information, même à des parties sans limite de calcul, sauf avec une probabilité négligeable.
4. Honest-verifier zero knowledge: Un protocole qui ne fournit aucune connaissance aux parties limitées dans le temps polynomial, si elles agissent comme spécifié par le protocole.

Que diriez-vous du fait que le calcul permanent est # P-complet mais déterminant de l'informatique - une manière dont le fonctionnement plus étrange se trouve être dans la classe NC?

Cela semble plutôt étrange - il ne devait pas en être ainsi (ou peut-être que oui ;-))

Le problème de programmation linéaire peut être résolu en temps (faiblement) polynomial. Cela semble très surprenant: pourquoi pourrions-nous en trouver un parmi un nombre exponentiel de sommets d'un polytope de grande dimension? Pourquoi pourrions-nous résoudre un problème si ridiculement expressif?

Sans parler de tous les programmes linéaires de taille exponentielle que nous pouvons résoudre en utilisant la méthode ellipsoïde et les oracles de séparation, et d'autres méthodes (ajout de variables, etc.). Par exemple, il est étonnant qu'un LP avec un nombre exponentiel de variables comme la relaxation de Karmakar-Karp de Bin Packing puisse être efficacement approché.

Chaque fois que j'enseigne des automates, je demande toujours à mes élèves s'ils trouvent surprenant que le non-déterminisme n'ajoute aucun pouvoir aux automates à états finis (c'est-à-dire que pour chaque NFA, il existe un équivalent - peut-être beaucoup plus grand - DFA). Environ la moitié des élèves disent être surpris, alors voilà. [J'ai moi-même perdu la "sensation" de ce qui est surprenant au niveau de l'intro.]

$R\neq RE$

J'ai trouvé paradoxal le simple système de cryptage à clé publique avec un mécanisme de déchiffrement à double trappe et ses applications , car il s'agit d'un schéma sécurisé de texte chiffré choisi et adaptatif qui est homomorphe.