Finite Herbrand Models for Restricted First-Order Clauses

Autor: Borgwardt, Stefan, Morawska, Barbara

We call a Herbrand model of a set of first-order clauses finite, if each of the predicates in the clauses is interpreted by a finite set of ground terms. We consider first-order clauses with the signature restricted to unary predicate and function sy

Externí odkaz: https://tud.qucosa.de/id/qucosa%3A79619
https://tud.qucosa.de/api/qucosa%3A79619/attachment/ATT-0/

EXPTIME Hardness of an n by n Custodian Capture Game

Autor: Fumitaka Ito, Masahiko Naito, Naoyuki Katabami, Tatsuie Tsukiji

Publikováno v: Algorithms, Vol 14, Iss 3, p 70 (2021)

Custodian capture occurs when a player has placed two of his pieces on the opposite sides of an orthogonal line of the opponent’s men. Each piece moves like the rook in Chess. Different cultures played it from pre-modern times in two-player strateg

Externí odkaz: https://doaj.org/article/e8c4838a5525469d88d48a52af8125ed

Reachability games with relaxed energy constraints

Autor: Nicolas Markey, Loïc Hélouët, Ritam Raha

Publikováno v: Information and Computation
Information and Computation, 2022, 285B, ⟨10.1016/j.ic.2021.104806⟩
Electronic Proceedings in Theoretical Computer Science, Vol 305, Iss Proc. GandALF 2019, Pp 17-33 (2019)
Information and Computation, Elsevier, 2021, pp.1-20. ⟨10.1016/j.ic.2021.104806⟩
GandALF 2019-Tenth International Symposium on Games, Automata, Logics, and Formal Verification
GandALF 2019-Tenth International Symposium on Games, Automata, Logics, and Formal Verification, Sep 2019, Bordeaux, France. pp.17-33, ⟨10.4204/EPTCS.305.2⟩
Information and computation
GandALF

We study games with reachability objectives under energy constraints. We first prove that under strict energy constraints (either only lower-bound constraint or interval constraint), those games are LOGSPACE-equivalent to energy games with the same e

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c441a8bf41ca53548c2f370d0d363635
https://inria.hal.science/hal-03482420/document

Review of the Solutions of the Clay Millennium Problem about P ≠ NP =EXPTIME

Autor: Konstantinos E. Kyritsis

Publikováno v: WORLD JOURNAL OF RESEARCH AND REVIEW
WORLD JOURNAL OF RESEARCH AND REVIEW, https://www.wjrr.org/, 2021, 13 (3), pp.21-26. ⟨10.31871/WJRR.13.3.8⟩
www.wjrr.org

In this paper I present probably the simplest possible abstract formal proof that P ≠ NP, and NP=EXPTIME, in the context of the Zermelo-Frankel set theory and deterministic Turing machines. My previous publications about the solution of the P vs NP

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::31d7e267d92873669b1290c8d5224e44
https://hal.archives-ouvertes.fr/hal-03360609/file/WJRR1303008_3dClay_millenium_review_30_9_21.pdf

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.