How Easy it is to Know How: An Upper Bound for the Satisfiability Problem

被引：0

作者：

Areces, Carlos ^{[1
,2
]}

Cassano, Valentin ^{[1
,2
,3
]}

Castro, Pablo F. ^{[1
,3
]}

Fervari, Raul ^{[1
,2
,4
]}

Saravia, Andres R. ^{[1
,2
]}

机构：

[1] Consejo Nacl Invest Cient & Tecn CONICET, Buenos Aires, DF, Argentina

[2] UNC, Cordoba, Argentina

[3] UNRC, Rio Cuarto, Argentina

[4] Guangdong Technion Israel Inst Technol GTIIT, Shantou, Peoples R China

来源：

LOGICS IN ARTIFICIAL INTELLIGENCE, JELIA 2023 | 2023年 / 14281卷

关键词：

Knowing How; Complexity; Satisfiability;

D O I：

10.1007/978-3-031-43619-2_28

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We investigate the complexity of the satisfiability problem for a modal logic expressing 'knowing how' assertions, related to an agent's abilities to achieve a certain goal. We take one of the most standard semantics for this kind of logics based on linear plans. Our main result is a proof that checking satisfiability of a 'knowing how' formula can be done in Sigma(P)(2). The algorithm we present relies on eliminating nested modalities in a formula, and then performing multiple calls to a satisfiability checking oracle for propositional logic.

引用

页码：405 / 419

页数：15

共 25 条

[21] How to exploit fitness landscape properties of timetabling problem: A new operator for quantum evolutionary algorithm
Najaran, Mohammad Hassan Tayarani
EXPERT SYSTEMS WITH APPLICATIONS, 2021, 168
[22] How to Get What You Want When You Do Not Know What You Want: A Model of Incentives, Organizational Structure, and Learning
Marengo, Luigi
Pasquali, Corrado
ORGANIZATION SCIENCE, 2012, 23 (05) : 1298 - 1310
[23] From a Logical Approach to Internal States of Hash Functions How SAT Problem Can Help to Understand SHA-☆ and MD☆
Legendre, Florian
Dequen, Gilles
Krajecki, Michael
PROCEEDINGS OF THE 10TH INTERNATIONAL CONFERENCE ON SECURITY AND CRYPTOGRAPHY (SECRYPT 2013), 2013, : 435 - 443
[24] Something wicked this way comes: How well did UK newspapers support the public debate of Avian Influenza as a wicked problem?
Garnier, Marie
Tamas, Peter A.
van Wessel, Margit
van Bommel, Severine
JOURNALISM, 2022, 23 (09) : 2012 - 2035
[25] How do older and young adults start searching for information? Impact of age, domain knowledge and problem complexity on the different steps of information searching
Sanchiz, M.
Chevalier, A.
Amadieu, F.
COMPUTERS IN HUMAN BEHAVIOR, 2017, 72 : 67 - 78

← 1 2 3 →