Eötvös number: Difference between revisions
Jump to navigation
Jump to search
en>Bibcode Bot m Adding 0 arxiv eprint(s), 1 bibcode(s) and 0 doi(s). Did it miss something? Report bugs, errors, and suggestions at User talk:Bibcode Bot |
en>Ugog Nizdast m Reverted 1 edit by 187.139.212.71 identified as test/vandalism using STiki |
||
| Line 1: | Line 1: | ||
In [[computational complexity theory]], the [[complexity class]] '''TFNP''' is a subclass of [[FNP (complexity)|FNP]] where a solution is guaranteed to exist. It stands for "Total Function Nondeterministic Polynomial." | |||
:A binary relation P(''x'',''y'') is in '''TFNP''' if and only if there is a deterministic polynomial time algorithm that can determine whether P(''x'',''y'') holds given both ''x'' and ''y'', and for every ''x'', there exists a ''y'' such that P(''x'',''y'') holds. | |||
The job of an ''TFNP'' algorithm is to establish, given an ''x'' give one possible value for a ''y'' such that P(''x'',''y'') holds. | |||
[[FP (complexity)|FP]] is a subclass of TFNP. TFNP also contains subclasses [[PLS (complexity)|PLS]], [[PPA (complexity)|PPA]], [[PPAD (complexity)|PPAD]], and [[PPP (complexity)|PPP]]. | |||
TFNP = FP would imply [[P (complexity)|P]] = [[NP (complexity)|NP]] <math>\cap</math> [[Co-NP|coNP]], and therefore that factoring and simplex pivoting are in P. | |||
In contrast to FNP, there is no known recursive enumeration of machines for problems in TFNP. It seems that such classes, and therefore TFNP, do not have complete problems. | |||
== References == | |||
* Megiddo and Papadimitriou. [http://citeseer.ist.psu.edu/megiddo89note.html A Note on Total Functions, Existence Theorems and Computational Complexity (1989)]. | |||
[[Category:Complexity classes]] | |||
Revision as of 17:10, 14 December 2013
In computational complexity theory, the complexity class TFNP is a subclass of FNP where a solution is guaranteed to exist. It stands for "Total Function Nondeterministic Polynomial."
- A binary relation P(x,y) is in TFNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(x,y) holds given both x and y, and for every x, there exists a y such that P(x,y) holds.
The job of an TFNP algorithm is to establish, given an x give one possible value for a y such that P(x,y) holds.
FP is a subclass of TFNP. TFNP also contains subclasses PLS, PPA, PPAD, and PPP.
TFNP = FP would imply P = NP coNP, and therefore that factoring and simplex pivoting are in P.
In contrast to FNP, there is no known recursive enumeration of machines for problems in TFNP. It seems that such classes, and therefore TFNP, do not have complete problems.
References
- Megiddo and Papadimitriou. A Note on Total Functions, Existence Theorems and Computational Complexity (1989).