In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analogue of one of the most studied problems in parameterized complexity, the notion of weighted Fagin-definability, which is formulated in terms of satisfaction of first-order formulas with free relation variables. We focus on the parameterized complexity of weighted team definability for a fixed formula phi of central team-based logics. Given a first-order structure A and the parameter value k as input, the question is to determine whether A,T models phi for some team T of size k. We show several results on the complexity of this problem for dependence, independence, and inclusion logic formulas. Moreover, we also relate the complexity of weighted team definability to the complexity classes in the well-known W-hierarchy as well as paraNP.
翻译：在文章中,我们研究了加权小组对团队语义学逻辑定义的复杂性,这是一个自然的类似问题,是参数复杂度研究最多的问题之一,即加权法基-可定义性概念,该概念是以一阶公式与自由关系变量的满意度来拟订的,我们侧重于加权小组对基于团队逻辑的固定公式的固定公式的可定义性的参数复杂性。考虑到第一级结构A和作为投入的参数值k,问题在于确定某些规模为k的T组是否采用A、T型模型。我们就依赖性、独立性和包容性逻辑公式的复杂程度展示了若干结果。此外,我们还将加权小组的可定义复杂性与众所周知的W级和parNP的复杂类别联系起来。
相关内容
微信扫码咨询专知VIP会员