1
$\begingroup$

The notion of low information content is used to describe sparse sets and tally sets in complexity theory. Such sets can not be $NP$-complete unless $P=NP$. I am not aware of a formal information-theoretic definition which I hope would lead to insights into the phenomena of complexity hierarchy inside $NP$.

What are the barriers to measuring the information content of computational problems? ( perhaps using ideas inspired by notions like topological entropy or Shannon probabilistic entropy)

Note that I am interested in worst-case computational information content. The term low information content probably motivated by the widely believed conjecture that sparse sets can not be $NP$-complete ( unless $P = NP$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.