Zobrazeno 1 - 10
of 474
pro vyhledávání: '"Turing reduction"'
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Francesco Belardinelli, Stéphane Demri
Publikováno v:
Artificial Intelligence
Artificial Intelligence, 2021, 300, pp.103557. ⟨10.1016/j.artint.2021.103557⟩
Artificial Intelligence, Elsevier, 2021, 300, pp.103557. ⟨10.1016/j.artint.2021.103557⟩
Artificial Intelligence, 2021, 300, pp.103557. ⟨10.1016/j.artint.2021.103557⟩
Artificial Intelligence, Elsevier, 2021, 300, pp.103557. ⟨10.1016/j.artint.2021.103557⟩
International audience; The resource-bounded alternating-time temporal logic RB±ATL combines strategic reasoning with reasoning about resources. Its model-checking problem is known to be 2EXPTIME-complete (the same as its proper extension RB±ATL$^
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0f79213dfba908036b155521646e7073
https://hal.science/hal-03298703/document
https://hal.science/hal-03298703/document
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
De Bona, Glauber
Este trabalho estuda o problema da Satisfazibilidade Probabilística (PSAT), revendo a sua solução via programação linear, além de propor novos algoritmos para resolvê-lo através da redução ao SAT. Construímos uma redução polinomial do PS
Autor:
Borut Robič
Publikováno v:
The Foundations of Computability Theory ISBN: 9783662624203
The Foundations of Computability Theory ISBN: 9783662448076
The Foundations of Computability Theory ISBN: 9783662448076
At this point we only know of two degrees of unsolvability: the T-degree shared by all the decidable decision problems, and the T-degree shared by all undecidable decision problems that are T-equivalent to the Halting Problem. In this chapter we will
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::12e9b84d44c6c1f6c55ed260d8a89072
https://doi.org/10.1007/978-3-662-62421-0_12
https://doi.org/10.1007/978-3-662-62421-0_12
Publikováno v:
Theory of Computing Systems. 63:809-832
We show that the conjugacy problem in a wreath product A ≀ B is uniform-TC0-Turing-reducible to the conjugacy problem in the factors A and B and the power problem in B. If B is torsion free, the power problem in B can be replaced by the slightly we
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::05dd4e5146730ac1069d66149d5e2187
https://doi.org/10.1007/s00224-018-9849-2
https://doi.org/10.1007/s00224-018-9849-2
Autor:
Ilyes Khennak, Habiba Drias
Publikováno v:
International Journal of Information Retrieval Research. 7:1-21
During the last few years, it has become abundantly clear that the technological advances in information technology have led to the dramatic proliferation of information on the web and this, in turn, has led to the appearance of new words in the Inte
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f91166458f09d313b8d6a657b9885bd4
https://doi.org/10.4018/ijirr.2017070101
https://doi.org/10.4018/ijirr.2017070101
Autor:
Michael Grabchak, Victor Cosme
Publikováno v:
Communications in Statistics - Simulation and Computation. 46:4199-4209
Turing's formula is an amazing result that allows one to estimate the probability of observing something that has not been observed before. After a brief review of the literature, we perform a simulation study to better understand how well this formu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ce5398f3933e6979c89503649231c241
https://doi.org/10.1080/03610918.2015.1109658
https://doi.org/10.1080/03610918.2015.1109658
Autor:
Tomoyuki Yamakami
Publikováno v:
Unconventional Computation and Natural Computation ISBN: 9783030193102
UCNC
UCNC
Theory of relativization provides profound insights into the structural properties of various collections of mathematical problems by way of constructing desirable oracles that meet numerous requirements of the problems. This is a meaningful way to t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0772c4a9ec6cbc183a500f03a7305687
https://doi.org/10.1007/978-3-030-19311-9_20
https://doi.org/10.1007/978-3-030-19311-9_20
Autor:
Alberto Ciaffaglione
Publikováno v:
Science of Computer Programming. 126:31-51
We adopt corecursion and coinduction to formalize Turing Machines and their operational semantics in the Coq proof assistant. By combining the formal analysis of converging and diverging computations, via big-step and small-step predicates, our appro
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::906f09e2c6fc73912a2eb4b0ef174a19
https://doi.org/10.1016/j.scico.2016.02.004
https://doi.org/10.1016/j.scico.2016.02.004