Karp reduction (polynomial-time many one) is used in complexity theory to define NP-completeness. However, Cook reductions (polynomial-time Turing) is more powerful and intuitive from information theoretic perspective since it could offer an insight into the information content of hard sets in NP.

Intuitively, if we say problem $A$ Cook reduces to problem $B$ then the information content of set $A$ should be proportional to the number of calls made to $B's$ oracle. For instance, we have a truth-table (Cook) reduction from Graph Automorphism problem to Graph Isomorphism problem but no such reduction in the opposite direction is known. I am interested in techniques for lower bounding the number of calls to GA's oracle (in possible Turing reduction from GI to GA).

Why is it hard to find lower bounds by lower bounding the required number of calls to $B's$ oracle? Is there an intuition that supports $P^{GI} \ne P^{GA}$?

  • 1
    $\begingroup$ A strong lower bound would imply, in particular, that graph automorphism is not in P. $\endgroup$ – Yuval Filmus Sep 12 '15 at 12:51
  • $\begingroup$ Mixing information theory and NP hardness like this can lead your intuition astray. For instance, factoring a product of two primes ($n=pq$) is hard, so given $n$ it's hard to recover $p$ and $q$, but information-theoretically the number $n$ contains exactly as much information as the two primes $p$ and $q$. I don't think your statements about "information content" are correct. It sounds like your real question has to do with bounding the number of oracle calls, so bringing information theory into it seems like a mistake. I suspect information-theoretic intuition will be misleading. $\endgroup$ – D.W. Sep 13 '15 at 0:22
  • $\begingroup$ @D.W. I am not referring to standard information theory. I am trying to come up with a measure for computational information. Possibly similar notions in the literature include computational entropy. $\endgroup$ – Mohammad Al-Turkistany Sep 13 '15 at 1:49
  • $\begingroup$ @D.W. As for factoring, let me disagree with you, two m-bits factors contain more computational information per bit than the 2m-bits number n. That is the reason for the hardness of finding two equal-size factors of a given number n. $\endgroup$ – Mohammad Al-Turkistany Sep 13 '15 at 2:06

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.