2
$\begingroup$

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.

$\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.