I have a question about the following question and its answer.

Status on circuit lower bounds for polylog-bounded depth circuits

In the above question, it is asked about methods to prove lower bounds for poly-log depth boolean circuits.

Jukna's kindful answer suggests two methods: one is matrix rigidity and the other is $t(G)$ which is the smallest number $t$ such that $G$ can be written as an intersection of $t$ bipartite graphs, each being a union of at most $t$ complete bipartite graphs.

Anyone considering about proofs of circuit lower bounds can not evade the "Natural Proof". In 1994, Razborov and Rudich proved that we can not take any approach satisfying the following three conditions:

  1. Constructivity: hard property of $f$ which is a boolean function we try to prove its hardness for arbitrary circuit in $\mathcal{C}$ can be computed by poly-time in the size of truth table of boolean function.

  2. Largeness: hard property of $f$ is easy to find in the sence of random function: the probability which randomly chosen boolean function from the family of all boolean function is at least $2^{-Cn}$

  3. Useful: hard property can not be dealt with by any circuit in $\mathcal{C}$

My question is:

Question1: Can bounding the two quantity that is matrix rigidity and $t(G)$ breaking the conditions of Natural Proofs?

Question2: At this moment, is there a method which we guarantee (or may have some hope) that the way is not a kind of natural proofs, if the answer of Question1 is NO?



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.