The PCP-like Theorem for Sub-linear Time Inapproximability
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911744867172352 |
|---|---|
| author | Ma, Hengzhao Li, Jianzhong |
| author_facet | Ma, Hengzhao Li, Jianzhong |
| contents | In this paper we propose the PCP-like theorem for sub-linear time inapproximability. Abboud et al. have devised the distributed PCP framework for proving sub-quadratic time inapproximability. Here we try to go further in this direction. Staring from SETH, we first find a problem denoted as Ext-$k$-SAT, which can not be computed in linear time, then devise an efficient MA-like protocol for this problem. To use this protocol to prove the sub-linear time inapproximability of other problems, we devise a new kind of reduction denoted as Ext-reduction, and it is different from existing reduction techniques. We also define two new hardness class, the problems in which can be computed in linear-time, but can not be efficiently approximated in sub-linear time. Some problems are shown to be in the newly defined hardness class. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2107_01520 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The PCP-like Theorem for Sub-linear Time Inapproximability Ma, Hengzhao Li, Jianzhong Computational Complexity In this paper we propose the PCP-like theorem for sub-linear time inapproximability. Abboud et al. have devised the distributed PCP framework for proving sub-quadratic time inapproximability. Here we try to go further in this direction. Staring from SETH, we first find a problem denoted as Ext-$k$-SAT, which can not be computed in linear time, then devise an efficient MA-like protocol for this problem. To use this protocol to prove the sub-linear time inapproximability of other problems, we devise a new kind of reduction denoted as Ext-reduction, and it is different from existing reduction techniques. We also define two new hardness class, the problems in which can be computed in linear-time, but can not be efficiently approximated in sub-linear time. Some problems are shown to be in the newly defined hardness class. |
| title | The PCP-like Theorem for Sub-linear Time Inapproximability |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2107.01520 |