Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.01812 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929657599754240 |
|---|---|
| author | Moshkov, Mikhail |
| author_facet | Moshkov, Mikhail |
| contents | In this paper, we study three algorithmic problems involving computation trees: the optimization, solvability, and satisfiability problems. The solvability problem is concerned with recognizing computation trees that solve problems. The satisfiability problem is concerned with recognizing sentences that are true in at least one structure from a given set of structures. We study how the decidability of the optimization problem depends on the decidability of the solvability and satisfiability problems. We also consider various examples with both decidable and undecidable solvability and satisfiability problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_01812 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithmic Problems for Computation Trees Moshkov, Mikhail Logic in Computer Science In this paper, we study three algorithmic problems involving computation trees: the optimization, solvability, and satisfiability problems. The solvability problem is concerned with recognizing computation trees that solve problems. The satisfiability problem is concerned with recognizing sentences that are true in at least one structure from a given set of structures. We study how the decidability of the optimization problem depends on the decidability of the solvability and satisfiability problems. We also consider various examples with both decidable and undecidable solvability and satisfiability problems. |
| title | Algorithmic Problems for Computation Trees |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2501.01812 |