Game semantics approach to higher-order complexity

作者：

Highlights：

• We define a notion of size and complexity for strategies in sequential games.

• This defines a notion of complexity for PCF functions.

• The corresponding higher-order polynomial time complexity class contains BFF.

摘要

•We define a notion of size and complexity for strategies in sequential games.•This defines a notion of complexity for PCF functions.•The corresponding higher-order polynomial time complexity class contains BFF.

论文关键词：Higher-order,Complexity,Game semantics,bff,pcf

论文评审过程：Received 16 March 2015, Revised 27 January 2017, Accepted 4 February 2017, Available online 14 February 2017, Version of Record 11 April 2017.

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