A Note on the NP-Hardness of PARTITION Via First-Order Projections
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918263769792512 |
|---|---|
| author | Iturralde, Paúl Risco |
| author_facet | Iturralde, Paúl Risco |
| contents | In the article ''On the (Non) NP-Hardness of Computing Circuit Complexity'', Murray and Williams imply the PARTITION decision problem is not known to be NP-hard via $2^{n^{o(1)}}$-size AC0 reductions. In this note, we show PARTITION is NP-hard via first-order projections. Basically, we slightly modify well-known reductions from 3SAT to SUBSET-SUM and from SUBSET-SUM to PARTITION, but do so in the context of descriptive computational complexity, i.e., we use first-order logical formulas to define them. Hardness under polynomial-size AC0 reductions follows because first-order reductions are a particular type of them. Thus, this note fills a gap in the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21448 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Note on the NP-Hardness of PARTITION Via First-Order Projections Iturralde, Paúl Risco Logic in Computer Science Computational Complexity F.4.0; F.1.3 In the article ''On the (Non) NP-Hardness of Computing Circuit Complexity'', Murray and Williams imply the PARTITION decision problem is not known to be NP-hard via $2^{n^{o(1)}}$-size AC0 reductions. In this note, we show PARTITION is NP-hard via first-order projections. Basically, we slightly modify well-known reductions from 3SAT to SUBSET-SUM and from SUBSET-SUM to PARTITION, but do so in the context of descriptive computational complexity, i.e., we use first-order logical formulas to define them. Hardness under polynomial-size AC0 reductions follows because first-order reductions are a particular type of them. Thus, this note fills a gap in the literature. |
| title | A Note on the NP-Hardness of PARTITION Via First-Order Projections |
| topic | Logic in Computer Science Computational Complexity F.4.0; F.1.3 |
| url | https://arxiv.org/abs/2512.21448 |