Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 5 of 5 for “"TFNP"”.
-
Variants of Pseudo-deterministic Algorithms and Duality in TFNP
We introduce a new notion of ``faux-deterministic'' algorithms for search problems in query complexity. Roughly, for a search problem $\cS$, a faux-deterministic algorithm is a probability distribution $\mathcal{A}$ over deterministic algorithms $A\in \mathcal{A}$ such that no computationally …
-
On the Black-Box Impossibility of Hardness in TFNP from One-Way Functions
The complexity class TFNP contains all NP search problems for which a solution is guaranteed to exist for every instance. A proof of totality is needed for every problem in TFNP, so syntactic subclasses (such as PLS, PPA, PPAD, PPP, and PWPP) categorize many problems in TFNP according to the …
-
Structural results for total search complexity classes with applications to game theory and optimisation
… lie in the class of total NP search problems (TFNP), namely the class of NP search problems that always have a solution. Importantly, these problems cannot be NP-hard unless NP = co-NP. Notable examples of TFNP problems include FACTORING (given a natural number, compute its prime factorisation) …
-
The Colorful Carathéodory Problem and its Descendants
… is contained in total function NP (TFNP), the class of NP search problems that always admit a solution. We show that ColorfulCarathéodory belongs to the intersection of two important subclasses of TFNP: the complexity classes polynomial-time parity argument on directed graphs (PPAD) …
-
Balance Problems for Integer Circuits and Separations of Relativized Conjectures on Incompleteness in Promise Classes
… that have optimal proof systems. - \(\mathsf{TFNP}\): there do not exist complete total polynomial search problems (also known as total NP search problems). - \(\mathsf{DisjNP}\) and \(\mathsf{DisjCoNP}\): There do not exist complete disjoint NP pairs (coNP pairs). - \(\mathsf{UP}\): UP does …