如何以这种方式定义此集合?

问题描述 投票:0回答:1

enter image description here

大家好,对法语文本表示抱歉,但对于那些不讲法语的人应该清楚。

我对此练习有问题,因为我不了解SATH的运作方式...这不是递归定义吗?有人有什么想法吗?谢谢!

complexity-theory turing-machines
1个回答
0
投票

我的法语有点生疏,但据我所知,问题是:

SATh定义为H,H定义为SATh。为什么这不是问题?

不会成为问题的唯一可能原因是,如果每次递归调用的问题大小都减小了;就是说,SATh是根据解决问题的较小实例的解决方案定义的,而H是根据解决SATh的问题较小实例的解决方案定义的,因此SATh(x)取决于H( y)和H(y)取决于SATh(z),并且x> = y> z或x> y> = z始终保持为真。

然后只有到那时,这才不是问题,因为递归链最终将达到一个基本案例(假设每个案例都有一个基本案例,此方法始终可以达到该基本案例;我假设上下文中的案例1、0和负数可能有一些特殊处理)。

© www.soinside.com 2019 - 2024. All rights reserved.