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 条

[1] How do we know how?
Toribio, Josefa
PHILOSOPHICAL EXPLORATIONS, 2008, 11 (01) : 39 - 52
[2] Propositional knowledge and know-how
John N Williams
Synthese, 2008, 165 : 107 - 125
[3] Propositional knowledge and know-how
Williams, John N.
SYNTHESE, 2008, 165 (01) : 107 - 125
[4] Linguistic know-how and the orders of language
van den Herik, Jasper C.
LANGUAGE SCIENCES, 2017, 61 : 17 - 27
[5] Know-how, intellectualism, and memory systems
De Brigard, Felipe
PHILOSOPHICAL PSYCHOLOGY, 2019, 32 (05) : 720 - 759
[6] New upper bound for the #3-SAT problem
Kutzkov, Konstantin
INFORMATION PROCESSING LETTERS, 2007, 105 (01) : 1 - 5
[7] Helplessness: The inability to know-that you don't know-how
Arieli, Amos
Ataria, Yochai
PHILOSOPHICAL PSYCHOLOGY, 2018, 31 (06) : 948 - 968
[8] Sporting knowledge and the problem of knowing how
Gunnar, Breivik
JOURNAL OF THE PHILOSOPHY OF SPORT, 2014, 41 (02) : III - III
[9] Implicit knowledge and motor skill: What people who know how to catch don't know
Reed, Nick
McLeod, Peter
Dienes, Zoltan
CONSCIOUSNESS AND COGNITION, 2010, 19 (01) : 63 - 76
[10] Advancing Acquisition of Business Know-How: Critical Learning Elements
Lainema, Timo
Lainema, Kirsi
JOURNAL OF RESEARCH ON TECHNOLOGY IN EDUCATION, 2007, 40 (02) : 183 - 198

← 1 2 3 →