Journal article icon

Journal article

Towards a unified complexity theory of total functions

Abstract:

The class TFNP, of NP search problems where all instances have solutions, appears not to have complete problems. However, TFNP contains various syntactic subclasses and important problems. We introduce a syntactic class of problems that contains these known subclasses, for the purpose of understanding and classifying TFNP problems. This class is defined in terms of the search for an error in a concisely-represented formal proof. Finally, the known complexity subclasses are based on existence ...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jcss.2017.12.003

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
ORCID:
0000-0002-5436-7890
Papadimitriou, CH More by this author
Publisher:
Elsevier Publisher's website
Journal:
Journal of Computer and System Sciences Journal website
Volume:
94
Pages:
167-192
Publication date:
2017-12-28
Acceptance date:
2017-12-22
DOI:
ISSN:
0022-0000
Pubs id:
pubs:820626
URN:
uri:24c14d24-74d2-44f1-8e4e-fe7c25395368
UUID:
uuid:24c14d24-74d2-44f1-8e4e-fe7c25395368
Local pid:
pubs:820626

Terms of use


Metrics



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

TO TOP