Er, if you think you have solved P = NP, then you most definitely have not solved P = NP.

Also, NP-Intermediate and quasi-polynomial are two very different things. E.g. prime factorization of $n$-digit numbers is, last I heard, known to require about $2^{\frac{n}3}$ operations hence is slower than any quasipolynomial algorithm, but it is almost certainly NP-intermediate rather than NP-complete.

Anyway what is the algorithm? It might (or might not) be enjoyable for us Codidacters to look at it…

Er, if you think you have solved P = NP, then you most definitely have not solved P = NP.

I know. I'm quite skeptical about it too. But the experiments so far are looking good. And the algorithm is so simple that its complexity seems trivial to see. I'm trying hard to prove myself wrong, but haven't been able. :)

prime factorization of n-digit numbers is, last I heard, known to require about 2^(n/3) operations hence is slower than any quasipolynomial algorithm,

I guess by "known to require" you mean no better algorithm is known to exist, rather than no better algorithm being possible. That's interesting. I was wondering what was the complexity of the best algorithm for NP-Complete.

but it is almost certainly NP-intermediate rather than NP-complete.

Let me insist in the question. Would NP-Complete being QP imply that NP-Intermediate being empty?

...

Anyway what is the algorithm? It might (or might not) be enjoyable for us Codidacters to look at it…

I'll publish it in a matter of weeks. I'd like to check a few things before that. But I'll certainly show the algorithm here.

If you email me (see my profile), I can show some large-ish maximum clique problems and solutions before showing the algorithm, which might help see if it might be correct or not.

@als Your interpretation of "known to require" is correct. And thanks for your offer wrt. the algorithm. I've made an incomplete answer below; unfortunately this is about the extent of my knowledge.

@alx How large are the clique decision problems your algorithm can solve? I could send a test case via, say, 0x0.st easily enough.

@clemen

I realized about a mistake in the algorithm. After fixing it, it's not logC(n)^logC(n), but more like n^logC(n). I need to re-evaluate how large it can solve. When I come back from Holiday, I'll run benchmarks on my desktop.

I'm using benchmarks from https://iridia.ulb.ac.be/~fmascia/maximum_clique/DIMACS-benchmark.

One interesting thing is that the bad algorithm passed all the benchmarks I had run with it, so it serves as a fast approximation. I only realized about the mistake by thinking about it.

What I miss in that site is benchmarks based on integer-factoring problems, which are believed to be the most difficult ones. That would allow me to test some cases close to the theoretical worst case.

For now, I consider http://iridia.ulb.ac.be/~fmascia/files/DIMACS/C500.9.clq to be the test that would determine whether I've found anything interesting or not. At the moment, I'm running smaller benchmarks to have an estimation of the time it will take to do that.

@alx: At the other site (https://cs.stackexchange.com/a/168703) there's a link to some resources for generating hard $n$-variable 3-SAT problems (which of course can be easily changed to maximal-clique problems with thrice the number of variables). Apparently it finds problems with as few as 100 variables (thus, 300 nodes) that are hard for current SAT solvers.

I've never worked with 3-SAT, so I don't know how to translate them. Are there any well-known translators?

Basically, for each conjunct of the form, say, $(x_i ∨ ¬x_j ∨ ¬x_k)$, make three new nodes labeled "$x_i$", "$¬x_j$", and "$¬x_k$". Then connect all nodes to each other, except for nodes labeled "$x_i$" and "$¬x_i$" for all $i$. See the Wikimedia diagram, which shows how the translation process works for $(x ∨ x ∨ y) ∧ (¬x ∨ ¬y ∨ ¬y) ∧ (¬x ∨ y ∨ y)$ (giving a 3-clique-finding problem in 9 nodes; in general a $k$-SAT formula with $n$ conjuncts will be an $n$-clique-finding problem in at most $kn$ nodes.)

The Wikimedia diagram seems to also not connect each group of three nodes between themselves. I should also not connect those, right?

Then, 3-SAT DIMACS files seem to look like

p cnf 600 2550
-567 -126 -483 0
-581 396 -247 0
-280 -301 -149 0
...

I interpret from that that '-' means negation, that I should ignore the 0s, and that each number is the node label.

Am I correct understanding the above as this?

!567 v !126 v !483
!581 v 396 v !247
!280 v !301 v !149

@aks Both of your statements are correct.

clemens‭

After fixing the bug:

In 1 second, I can solve problems of N~=60. In 1 minute, N~=90. In 1 hour, N~=125. In 1 day, N~=145.

I'm still evaluating how much I can do in a week and in a month (and in a year, but I probably won't wait that much).

All of these with p=0.9, which seems to be near the worst case.

The program I'm using is relatively unoptimized, and I'm running on a low-power computer, so these times can still be improved.

Oh, interesting! So, 3-SAT problems are solvable with something like an $O(1.3^n)$ algorithm. It could be that this algorithm is similar; I don't know.

In any case, just eyeballing it, it doesn't look like an $O(e^{\log^2 n})$ algorithm to me. Maybe asymptotic growth estimates for the revised algorithm would be a good question to ask on Codidact ?

In number of iterations of the recursive program, I can see the log quite clearly. In fact, while I could only bound it to N ^ (C * log(N)) in the revised algorithm, it still seems to be more like log(N) ^ (C2 * log(N), even though I'm not sure if I can prove that.

However, that bound is for the number of iterations. The work of each iteration is in O(N^5).

Thus, the total time is more like N^5 * N ^ (C * log(N)), and that grows relatively fast. Not as much as the exponential, but still. The 5 is hidden in that C constant, but it's still there.

I'll show below a run of the program, which might show why it looks so much quasi-polynomic (apart from the theoretical analysis on the algorithm).

(I'll still open a question about the analysis, as you suggested. But I'll do that after some more experiments finish.)

$ time npc-rand 100 0.9 0 | npc-solve 100 | wc -l
Size: 100
Frequency: 0.900000
Seed: 0
     13 0
    151 1
   1369 2
   8148 3
  18268 4
   8259 5
    464 6
     11 7
      9 8
      9 9
      9 10
      9 11
      9 12
      9 13
      9 14
      9 15
      9 16
      9 17
      9 18
      9 19
      9 20
      8 21
      7 22
      6 23
      5 24
      4 25
      3 26
      2 27
      2 28
      1 29
30

real	8m42.176s
user	6m55.197s
sys	1m52.039s

The 30 is the size of the solution. The numbers above are two columns. The second column is the depth of recursion, and the first column is the number of times each depth of recursion has been reached. So, the 0th (first) level is run 13 times; the next one 151 (which is roughly 13*13), and so on, but it's cut quite abruptly soon, at the 7th level of recursion, which is far from N, and closer to the logarithm of N in some base.

Here's another run, with a smaller problem:

$ time npc-rand 60 0.9 0 | npc-solve 60 | wc -l
Size: 60
Frequency: 0.900000
Seed: 0
      9 0
     39 1
     48 2
     11 3
      2 4
      2 5
      2 6
      2 7
      2 8
      2 9
      2 10
      2 11
      2 12
      2 13
      2 14
      2 15
      2 16
      2 17
      2 18
      2 19
      2 20
      2 21
      1 22
      1 23
24

real	0m1.142s
user	0m1.483s
sys	0m0.288s

@alx: Most interesting; thanks!

I'm pretty convinced it's correct. I've already published the algorithm as a question: https://math.codidact.com/posts/296074. Please have a look at it.

If it looks good, I'll publish my implementation (licensed as GPL-3.0-or-later) in a public mailing list (most likely, here: https://lore.kernel.org/linux-man) in a few days.