License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.37
URN: urn:nbn:de:0030-drops-83403
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8340/
Go to the corresponding LIPIcs Volume Portal

Goldberg, Paul W. ; Papadimitriou, Christos H.

Towards a Unified Complexity Theory of Total Functions

pdf-format:
LIPIcs-ITCS-2018-37.pdf (0.6 MB)

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 theorems that hold for finite structures; from Herbrand's Theorem, we note that such theorems must apply specifically to finite structures, and not infinite ones.

BibTeX - Entry

@InProceedings{goldberg_et_al:LIPIcs:2018:8340,
  author =	{Paul W. Goldberg and Christos H. Papadimitriou},
  title =	{{Towards a Unified Complexity Theory of Total Functions}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Anna R. Karlin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8340},
  URN =		{urn:nbn:de:0030-drops-83403},
  doi =		{10.4230/LIPIcs.ITCS.2018.37},
  annote =	{Keywords: Computational complexity, first-order logic, proof system, NP search functions, TFNP}
}

Keywords: Computational complexity, first-order logic, proof system, NP search functions, TFNP
Collection: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Issue Date: 2018
Date of publication: 12.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI