17. On SAT information content, its polynomial-time solvability and fixed code algorithms
Invited abstract in session FB-1: Complexity, stream Complexity.
Friday, 10:30 - 12:00Room: L226
Authors (first author is the speaker)
| 1. | Maciej Drozdowski
|
| Institute of Computing Science, Poznan University of Technology |
Abstract
The amount of information in satisfiability problem (SAT) is considered. Search problems, such as SAT, information content can be measured as the information in string relations. SAT can be polynomial-time solvable when the solving algorithm holds an exponential amount of information. It is established that SAT Kolmogorov complexity is constant. It is also 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. For more information see
https://doi.org/10.48550/arXiv.2401.00947
Keywords
- Combinatorial Optimization
- Algorithms
Status: accepted
Back to the list of papers