Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This post is about Natural Proofs barrier in computational complexity.

There are two recent papers related to this. They are:

  1. Amplifying lower bounds by means of self-reducibility by Eric Allender and Michal Koucký,

  2. Almost-natural proofs by Timothy Chow.

Alexander Razborov mentioned them at the end of his talk in the first Barriers Workshop at IAS in 2009. The video of his talk is available here. He mentioned that a possible way to respond to these would be to make the largeness condition relative. So here is my question:

Has there been any progress on this?

share|improve this question
1  
Relative in what sense? –  Andrej Bauer Jul 30 '10 at 9:01
    
As far as I understand, he was saying that one should redefine the largeness to be relative to the class of functions being attacked. His comments were very brief (last 5min of his talk). I will add a link to the video of his talk to the post. –  Kaveh Jul 31 '10 at 22:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.