On SAT information content, its polynomial-time solvability and fixed code algorithms
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916335716401152 |
|---|---|
| author | Drozdowski, Maciej |
| author_facet | Drozdowski, Maciej |
| contents | The amount of information in satisfiability problem (SAT) is considered. SAT can be polynomial-time solvable when the solving algorithm holds an exponential amount of information. It is also established that SAT Kolmogorov complexity is constant. It is argued that the amount of information in SAT grows at least exponentially with the size of the input instance. The amount of information in SAT is compared with the amount of information in the fixed code algorithms and generated over runtime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_00947 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On SAT information content, its polynomial-time solvability and fixed code algorithms Drozdowski, Maciej Computational Complexity Information Theory F.2 The amount of information in satisfiability problem (SAT) is considered. SAT can be polynomial-time solvable when the solving algorithm holds an exponential amount of information. It is also established that SAT Kolmogorov complexity is constant. It is argued that the amount of information in SAT grows at least exponentially with the size of the input instance. The amount of information in SAT is compared with the amount of information in the fixed code algorithms and generated over runtime. |
| title | On SAT information content, its polynomial-time solvability and fixed code algorithms |
| topic | Computational Complexity Information Theory F.2 |
| url | https://arxiv.org/abs/2401.00947 |