Insignificant Choice Polynomial Time

Reading the abstract, this seems to be a claim on P vs NP. Specifically, that P != NP. The claim goes through the front door, using descriptive complexity theory, claiming a formal system for P and then claiming that SAT can't be expressed in that system.

The main observations focus on broken symmetry. Polynomial-time algorithms often have to start by choosing some unit of work, but without a requirement that work units be ordered; therefore some choice is required in order to pick a starting work unit. For example, to process a graph, one usually must start by choosing an edge or vertex without limitation.

The claim is, effectively, that SAT requires significant choices to be made in which direction to compute in order to solve its instances in polynomial time.

I confess that, although I've read the proof, I neither am convinced by it nor can find problems with it. I need to study it more.

I'm not sure how the barriers are handled. The relativization barrier, I can imagine, is handled by showing that abstract state machines with oracular advice can turn seemingly-insignificant choices into significant choices, so that the proof doesn't relativize. I don't know about algebrization, though.

In terms of Impagliazzo's five worlds, this result would indicate that we are in Minicrypt or Cryptomania, as is commonly believed already.

The title seems innocent enough, but if I understand this correctly, this purports to be a proof of P != NP.

I'm not familiar with a lot of the stuff talked about in the paper, but it's still exciting to see another attempt at the P ?= NP problem. Of course, purported proofs (for both P = NP and P != NP) have been published before[0].

[0]: https://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Big if true.

Clicking around arXiv and google scholar, I get the sense the author is legitimate. But I wouldn't be surprised if some technical barrier was found by another expert. I don't think the author has published anything in complexity theory before, and the story of 'older academic attempts to enter new field with old tools, immediately solves most important problem in field' is a tad fishy to me, though not entirely without precedent. The idea sounds pretty cool though; I'd definitely prefer to be mistaken.

I am far from being an expert on descriptive complexity, and have only skimmed the paper. One spot jumped out at me as a potential error: on page 21, the sentence

"Next we exploit that a choice in state S will be insignificant iff all update sets in Delta_r(S) are isomorphic, so..."

seems suspicious to me. One direction is likely obvious (that an isomorphism between choices proves the insignificance of the choice), but the other direction seems likely to be untrue (if I am interpreting correctly).

Given the history of this problem, I will wait until I see experts excited about it before worrying about whether it might be a good argument.