If we consider polynomial-time (or log-space) computable reductions $<_p^m$ as transformations between computational problems, then the following definitions of known complexity classes suggest the conservation of information under "efficient" transformations. Assuming $P\ne NP$, it seems that information flows only from easy problems to hard problems thorough efficient reductions.

$P=\{L| L<_p Horn3SAT, \bar L <_p Horn3SAT \}$

$NP=\{L| L<_p 3SAT \}$

$CoNP=\{L| \bar L<_p 3SAT \}$

$NPC=\{L| L<_p 3SAT, 3SAT<_p L \}$

$PC=\{L| L<_p Horn3SAT, Horn3SAT<_p L \}$

Is there a notion of computational hardness in terms of information flow that explains this apparent asymmetry of information flow between natural computational problems?

I am aware of the theorem that $P=NP$ if and only if a sparse set is $NP$-complete. I'm looking for notions different than set sparsity.


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.