Karp–Lipton theorem | Wikipedia audio article
Channel: wikipedia tts
Date: 18/02/2019

This is an audio version of the Wikipedia Article:
https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem


00:02:34 1 Intuition
00:03:16 2 Self-reducibility
00:03:27 3 Proof of Karp–Lipton theorem
00:05:55 4 Another proof and Ssub2/subsupP/sup
00:09:07 4.1 AM = MA
00:13:17 5 Application to circuit lower bounds – Kannan's theorem
00:18:37 6 References
00:24:43 Application to circuit lower bounds – Kannan's theorem



Listening is a more natural way of learning, when compared to reading. Written language only began at around 3200 BC, but spoken language has existed long ago.

Learning by listening is a great way to:
- increases imagination and understanding
- improves your listening skills
- improves your own spoken accent
- learn while on the move
- reduce eye strain

Now learn the vast amount of general knowledge available on Wikipedia through audio (audio article). You could even learn subconsciously by playing the audio while you are sleeping! If you are planning to listen a lot, you could try using a bone conduction headphone, or a standard speaker instead of an earphone.

Listen on Google Assistant through Extra Audio:
https://assistant.google.com/services/invoke/uid/0000001a130b3f91
Other Wikipedia audio articles at:
https://www.youtube.com/results?search_query=wikipedia+tts
Upload your own Wikipedia articles through:
https://github.com/nodef/wikipedia-tts
Speaking Rate: 0.7615024559762327
Voice name: en-GB-Wavenet-C


"I cannot teach anybody anything, I can only make them think."
- Socrates


SUMMARY
=======
In complexity theory, the Karp–Lipton theorem states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then 

  
    
      
        
          Π
          
            2
          
        
        =
        
          Σ
          
            2
          
        
        
      
    
    {\displaystyle \Pi _{2}=\Sigma _{2}\,}
   and therefore 
  
    
      
        
          P
          H
        
        =
        
          Σ
          
            2
          
        
        .
        
      
    
    {\displaystyle \mathrm {PH} =\Sigma _{2}.\,}
  That is, if we assume that NP, the class of nondeterministic polynomial time problems, can be contained in the non-uniform polynomial time complexity class P/poly, then this assumption implies the collapse of the polynomial hierarchy at its second level. Such a collapse is believed unlikely, so the theorem is generally viewed by complexity theorists as evidence for the nonexistence of polynomial size circuits for SAT or for other NP-complete problems. A proof that such circuits do not exist would imply that P ≠ NP. As P/poly contains all problems solvable in randomized polynomial time (Adleman's theorem), the Karp–Lipton theorem is also evidence that the use of randomization does not lead to polynomial time algorithms for NP-complete problems.
The Karp–Lipton theorem is named after Richard M. Karp and Richard J. Lipton, who first proved it in 1980. (Their original proof collapsed PH to 
  
    
      
        
          Σ
          
            3
          
        
      
    
    {\displaystyle \Sigma _{3}}
  , but Michael Sipser improved it to 
  
    
      
        
          Σ
          
            2
          
        
      
    
    {\displaystyle \Sigma _{2}}
  .)
Variants of the theorem state that, under the same assumption, MA = AM, and PH collapses to SP2 complexity class. There are stronger conclusions possible if PSPACE, or some other complexity classes are assumed to have polynomial-sized circuits; see P/poly. If NP is assumed to be a subset of BPP (which is a subset of P/poly), then the polynomial hierarchy collapses to BPP. If coNP is assumed to be subset of NP/poly, then the polynomial hierarchy collapses to its third level.