Amount of information in SAT is estimated and compared with the amount of information in the fixed code algorithms. A remark on SAT Kolmogorov complexity is made. It is argued that SAT can be polynomial-time solvable, or not, depending on the solving algorithm information content.
翻译:暂无翻译