On the Complexity of Validity Degrees in Łukasiewicz Logic
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F20%3A00531136" target="_blank" >RIV/67985807:_____/20:00531136 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-030-51466-2_15" target="_blank" >http://dx.doi.org/10.1007/978-3-030-51466-2_15</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-51466-2_15" target="_blank" >10.1007/978-3-030-51466-2_15</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On the Complexity of Validity Degrees in Łukasiewicz Logic
Popis výsledku v původním jazyce
Lukasiewicz logic is an established formal system of manyvalued logic. Decision problems in both propositional and first-order case have been classified as to their computational complexity or degrees of undecidability. For the propositional fragment, theoremhood and provability from finite theories are coNP complete. This paper extends the range of results by looking at validity degree in propositional Lukasiewicz logic, a natural optimization problem to find the minimal value of a term under a finite theory in a fixed complete semantics interpreting the logic. A classification for this problem is provided using the oracle class FPNP, where it is shown complete under metric reductions.
Název v anglickém jazyce
On the Complexity of Validity Degrees in Łukasiewicz Logic
Popis výsledku anglicky
Lukasiewicz logic is an established formal system of manyvalued logic. Decision problems in both propositional and first-order case have been classified as to their computational complexity or degrees of undecidability. For the propositional fragment, theoremhood and provability from finite theories are coNP complete. This paper extends the range of results by looking at validity degree in propositional Lukasiewicz logic, a natural optimization problem to find the minimal value of a term under a finite theory in a fixed complete semantics interpreting the logic. A classification for this problem is provided using the oracle class FPNP, where it is shown complete under metric reductions.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA18-00113S" target="_blank" >GA18-00113S: Usuzování se stupňovanými vlastnostmi</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2020
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Beyond the Horizon of Computability
ISBN
978-3-030-51465-5
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
14
Strana od-do
175-188
Název nakladatele
Springer
Místo vydání
Cham
Místo konání akce
Salerno
Datum konání akce
29. 6. 2020
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—