Thesis icon

Thesis

Structural results for total search complexity classes with applications to game theory and optimisation

Abstract:

While the celebrated theory of NP-completeness has been very successful in explaining the intractability of many interesting problems, there still remain many natural and seemingly hard problems that are not known to be NP-hard. Several of these problems 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 (...

Expand abstract

Actions


Access Document


Files:

Authors


More by this author
Division:
MPLS
Department:
Computer Science
Oxford college:
St Anne's College
Role:
Author
ORCID:
0000-0001-5255-9349

Contributors

Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Supervisor
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Supervisor
More from this funder
Name:
Engineering and Physical Sciences Research Council
Funder identifier:
http://dx.doi.org/10.13039/501100000266
Funding agency for:
Hollender, A
Grant:
1892947
Programme:
Doctoral Studentship
Type of award:
DPhil
Level of award:
Doctoral
Awarding institution:
University of Oxford
Language:
English
Keywords:
Subjects:
Deposit date:
2021-10-29

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP