New paper on P vs NP

Lew Gordeew lew.gordeew at uni-tuebingen.de
Mon Jan 4 07:57:52 EST 2021


Zitat von "Timothy Y. Chow" <tchow at math.princeton.edu>:

> Lew Gordeew wrote:
>> I conclude that CLIQUE(k^4,k) is not solvable by polynomial-size  
>> Boolean circuits, and hence P is not NP. The entire proof is  
>> formalizable by standard methods in the exponential function  
>> arithmetic EFA.
>
> Can your proof be formalized in S_2^2?  If so, does that mean that  
> strong pseudorandom number generators do not exist?  And if so, can  
> you break the RSA cryptosystem?  That would certainly get people's  
> attention.
>
> Tim

No, I don't see how to seriously weaken EFA. Sorry.

Lew





More information about the FOM mailing list