"Insignificant Choice Polynomial Time" -- P != NP

Timothy Y. Chow tchow at math.princeton.edu
Tue May 19 13:26:39 EDT 2020


>> Posting for discussion by experts... A newest proof of P != NP:
>>
>> https://arxiv.org/abs/2005.04598
>> by Klaus-Dieter Schewe

This is surely wrong but unfortunately there's no a priori reason it has 
to be wrong, so one would have to dig through the paper to find the 
mistake.

The author doesn't mention graph canonization.  It's natural to ask if the 
author is claiming that graph canonization can be done in polynomial time. 
(This doesn't follow automatically from the existence of a logic capturing 
PTIME but it's a very closely related problem.)  If so, then maybe known 
hard cases for graph isomorphism can be enlisted to help detect the error 
in the argument.

Tim


More information about the FOM mailing list