📑 Table of Contents▼

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

modifier

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

modifier
 
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

modifier
  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.

📚 Artikel Terkait di Wikipedia

Hypothèse de Riemann

zeta-function, The Clarendon Press Oxford University Press, 1986 (ISBN 978-0-19-853369-6, MR 882550) (en) H. M. Edwards, Riemann's Zeta Function, New

Concours Eurovision de la chanson 2025

Vautrey, « Netherlands: AVROTROS questions whether Eurovision “still functions as an apolitical event” amidst Israel's participation », sur wiwibloggs

Langage de programmation dynamique

mot : function new_scanner (word) temp_function = function (input) scan_for_text (input, word) end function return temp_function end function La fonction

Conjecture de Pólya

vol. 5, no 02,‎ 1958, p. 141-145 (en) R. S. Lehman, « On Liouville's function », Mathematics of Computation, vol. 14, no 72,‎ 1960, p. 311-320 (lire

Capacité de diffusion du monoxyde de carbone

1056/nejm198705213162103) Bailey, « The Importance of the Assessment of Pulmonary Function in COPD », The Medical Clinics of North America, vol. 96, no 4,‎ 1er juillet

Variation totale d'une fonction

homonymes, voir Variation totale. Ne doit pas être confondu avec la variation totale d'une mesure. En mathématiques, la variation totale est liée à la structure

Solidity

true; } function allowance(address tokenOwner, address spender) public view returns (uint remaining) { return allowed[tokenOwner][spender]; } function approve(address

Fonction de demande hicksienne

totalité issu de l’article de Wikipédia en anglais intitulé « Hicksian demand function » (voir la liste des auteurs). Portail de l’économie Portail des mathématiques