Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909438494900224 |
|---|---|
| author | Cai, Jin-Yi Maran, Ashwin |
| author_facet | Cai, Jin-Yi Maran, Ashwin |
| contents | We introduce some polynomial and analytic methods in the classification program for the complexity of planar graph homomorphisms. These methods allow us to handle infinitely many lattice conditions and isolate the new P-time tractable matrices represented by tensor products of matchgates. We use these methods to prove a complexity dichotomy for $4 \times 4$ matrices that says Valiant's holographic algorithm is universal for planar tractability in this setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_17122 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Polynomial and analytic methods for classifying complexity of planar graph homomorphisms Cai, Jin-Yi Maran, Ashwin Computational Complexity We introduce some polynomial and analytic methods in the classification program for the complexity of planar graph homomorphisms. These methods allow us to handle infinitely many lattice conditions and isolate the new P-time tractable matrices represented by tensor products of matchgates. We use these methods to prove a complexity dichotomy for $4 \times 4$ matrices that says Valiant's holographic algorithm is universal for planar tractability in this setting. |
| title | Polynomial and analytic methods for classifying complexity of planar graph homomorphisms |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2412.17122 |