Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.jcss.2017.12.003 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
Computational complexity,First-order logic,Proof system,NP search functions,TFNP | Conference | 94 |
ISSN | Citations | PageRank |
0022-0000 | 1 | 0.35 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul W. Goldberg | 1 | 759 | 98.26 |
| Christos H. Papadimitriou | 2 | 1 | 1.02 |