PROFILPELAJAR.COM

TFNP

En théorie de la complexité computationnelle, la classe de complexité TFNP est la classe des problèmes fonctionnels totaux qui peuvent être résolus en temps polynomial non déterministe. C'est la classe des problèmes fonctionnels où on a la garantie d'avoir une réponse, et cette réponse peut être vérifiée en temps polynomial; ou encore, c'est le sous-ensemble de FNP où une solution est garantie. L'abréviation TFNP signifie "Total Function Nondeterministic Polynomial".

TFNP contient de nombreux problèmes naturels qui intéressent les informaticiens. Ces problèmes incluent la factorisation d'entiers, la recherche d'un équilibre de Nash et la recherche d'optima locaux. Il est largement supposé que TFNP contient des problèmes difficiles sur le plan informatique, et plusieurs de ces problèmes sont difficiles sous des hypothèses cryptographiques[1],[2]. Cependant, il n'y a pas de résultats connus de difficulté inconditionnelle pour TFNP. On ne pense pas que TFNP ait des problèmes complets[3].

Définition

La classe TFNP est définie comme suit :

Une relation binaire P(x, y) est dans TFNP si et seulement s'il existe un algorithme en temps polynomial déterministe qui peut déterminer si P(x, y) est vrai ou non, étant donné x et y, et pour chaque x, il existe un y dont la taille est bornée par un polynome en la taille de x tel que P(x, y) soit vérifié.

TFNP a été définie par Megiddo et Papadimitriou[4],[5].

Sous-classes notables

Schéma des inclusions entre sous-classes de TFNP. Une flèche allant de la classe A à la classe B indique que A est un sous-ensemble de B .

Les sous-classes de TFNP sont souvent définies par le théorème mathématique qui garantit l'existence d'une solution.

Une des sous-classes est PPA.

Notes et références

  1. ↑ Garg, Pandey, and Srinivasan. Revisiting Cryptographic Hardness of Finding a Nash Equilibrium. CRYPTO 2016.
  2. ↑ Habàcek and Yogev. Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds. SODA 2016.
  3. ↑ Goldberg and Papadimitriou. Towards a Unified Complexity Theory of Total Functions. 2018.
  4. ↑ Megiddo and Papadimitriou. A Note on Total Functions, Existence Theorems and Computational Complexity. Theoretical Computer Science 1989.
  5. ↑ Johnson, Papadimitriou, and Yannakakis. How Easy is Local Search?. Journal of Computer System Sciences, 1988.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.