"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