25. SAT Information size and its implications for industrial optimization
Invited abstract in session WA-38: Industrial Optimization, stream Data Science meets Optimization.
Wednesday, 8:30-10:00Room: Michael Sadler LG19
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. It is argued that the amount of information in SAT grows at least exponentially with the size of the input instance. This is juxtaposed with the limited information content of the input instances, algorithms and external information sources that can be used at the runtime. It is argued that this available information quantity, in some cases, is insufficient in solving SAT. It is also claimed that combinatorial problems like SAT, are ultimately not learnable. This poses a question of the scalability of, e.g., machine learning methods in solving hard combinatorial problems.
Keywords
- Combinatorial Optimization
- Complexity and Approximation
- Industrial Optimization
Status: accepted
Back to the list of papers