Towards a unified complexity theory of total functions

作者：

Highlights：

• We extend and develop the general theory of TFNP, i.e. NP total search problems.

• We propose a new syntactic class PTFNP containing known syntactic TFNP subclasses.

• PTFNP is characterised by an easily-understood and explicitly-defined problem.

• We highlight the applicability of the literature on Bounded Arithmetic to variants of this problem.

摘要

•We extend and develop the general theory of TFNP, i.e. NP total search problems.•We propose a new syntactic class PTFNP containing known syntactic TFNP subclasses.•PTFNP is characterised by an easily-understood and explicitly-defined problem.•We highlight the applicability of the literature on Bounded Arithmetic to variants of this problem.

论文关键词：Computational complexity,First-order logic,Proof system,NP search functions,TFNP

论文评审过程：Received 2 May 2017, Revised 20 December 2017, Accepted 22 December 2017, Available online 28 December 2017, Version of Record 14 March 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.12.003