Karp's NP-complete problems over first-order definable structures 702AF3E4AF
| URI | m2://res/702AF3E4AF |
|---|---|
| Kind | preprint |
| Creators | Aidan Healy, Bartek Klin |
| Date | 2026-09-29 |
| MSC | 03-XX |
| Subjects | arxiv math.LO, arxiv cs.CC, arxiv cs.LO |
| Scope | in |
Expressions
e1: version, preprint
| Language | en |
|---|---|
| Date | 2026-09-29 |
| Ids | arXiv 2609.38436, zbl_id 8243909 |
Items in this resource
The mentions of the inventory that name this resource. Each name links to the card of its inventory row.
| Item | Kind | Where | Source |
|---|---|---|---|
| 1PDMHARSF5 | statement | theorem 7.10 | arxiv |
| \probname{CliqueCover | problem | problem 4.11 | arxiv |
| 34TV5GN5ZX | statement | lemma 7.2 | arxiv |
| 3ZCVT89PQM | statement | theorem 5.3 | arxiv |
| 4JPQRMKG5W | statement | lemma 4.1 | arxiv |
| 7KYRC5WR2R | statement | theorem 7.3 | arxiv |
| \probname{ExactCover | problem | problem 3.1 | arxiv |
| AJH695G9RZ | statement | theorem 3.16 | arxiv |
| \probname{FeedbackArcSet | problem | problem 4.8 | arxiv |
| \probname{SetPacking | problem | problem 5.4 | arxiv |
| C4SS9PMAC5 | statement | theorem 3.8 | arxiv |
| \probname{MaxCut | problem | problem 6.3 | arxiv |
| CJNMEW955Y | statement | theorem 5.5 | arxiv |
| DFE4G3ZQSA | statement | theorem 3.17 | arxiv |
| DQ7CZH1AGR | statement | theorem 7.11 | arxiv |
| EFSK4BN69S | statement | theorem 3.19 | arxiv |
| EMMYCGJ6P9 | example | example 1.2 | arxiv |
| \probname{VertexCover | problem | problem 4.6 | arxiv |
| \probname{0-1-ILP | problem | problem 3.13 | arxiv |
| G37ZQGHPXW | statement | theorem 7.9 | arxiv |
| \probname{Domino | problem | problem 3.2 | arxiv |
| JNQ5VDSY5K | statement | theorem 7.8 | arxiv |
| \probname{Colorability | problem | problem 4.10 | arxiv |
| KB7CS9WN6Y | statement | theorem 4.9 | arxiv |
| KF5M5D5C9D | statement | theorem 5.7 | arxiv |
| KJ8BTM4AWR | statement | lemma 5.2 | arxiv |
| M9RZ2GZKGQ | statement | lemma 4.2 | arxiv |
| \probname{(Un)DirectedHamiltonicity | problem | problem 3.15 | arxiv |
| \probname{ExactTupleCover | problem | problem 3.5 | arxiv |
| \probname{SteinerTree | problem | problem 6.1 | arxiv |
| MT1PZJK0BQ | statement | theorem 7.7 | arxiv |
| NDJW9QWWAN | statement | theorem 3.3 | arxiv |
| NGA9NZGW2X | statement | theorem 6.2 | arxiv |
| \probname{3-Sat | problem | problem 4.4 | arxiv |
| PSP9WTVCRX | statement | theorem 4.5 | arxiv |
| R4018EA880 | example | example 1.1 | arxiv |
| R9NTDJ1RKM | statement | corollary 3.6 | arxiv |
| \probname{SetCovering | problem | problem 5.6 | arxiv |
| SKE89D3Y83 | statement | theorem 3.14 | arxiv |
| T21N1YWAK8 | statement | theorem 4.12 | arxiv |
| T3EZ4S0X63 | statement | theorem 7.4 | arxiv |
| T7S41YHF0V | statement | theorem 7.12 | arxiv |
| V49ZX6E1P9 | statement | lemma 7.1 | arxiv |
| VMHM8NF0GT | statement | theorem 4.3 | arxiv |
| \probname{FeedbackVertexSet | problem | problem 4.7 | arxiv |
| VYTS9K7PER | statement | theorem 7.6 | arxiv |
| \probname{HittingSet | problem | problem 3.7 | arxiv |
| WC1V3TZM6Z | statement | theorem 7.5 | arxiv |
| \probname{Clique | problem | problem 5.1 | arxiv |
| XTTSKJAAWD | statement | theorem 3.11 | arxiv |
| \probname{CNFSat | problem | problem 3.10 | arxiv |
| \probname{3DMatching | problem | problem 3.18 | arxiv |
Catalogue records
- arxiv: 2609.38436 (work)
- zbmath_search: 8243909 (work)