[js8]

If everybody considers P=NP a crackpot territory, then it will never happen, by definition. On the contrary, I think to believe that the sets described by NP-complete instances are somehow inherently "undescribable" (as is implied by naturalization) is crackpottery also.

But regardless, it's important to realize that modern cryptography relies on a hypothesis. It might be effectively true for now, but it might not in the future.

> Btw, if your polynomial algorithm for NP is any good, you should be able to break any encryption at all.

In theory, yes, in practice, there is a pretty big difference between "I think I just discovered how to do Gaussian elimination to solve linear equations" and "I can routinely solve sparse linear systems with millions of variables". Historically, it wasn't done by a single individual in a span of couple years.

[eru]

> If everybody considers P=NP a crackpot territory, then it will never happen, by definition.

Oh, sorry, that's not what I meant to say. To be less vague, 'Practical P=NP is a very real possibility' is fine. 'Practical P=NP is a very real possibility (I am just testing a new algorithm)' is crackpot territory.

> But regardless, it's important to realize that modern cryptography relies on a hypothesis. It might be effectively true for now, but it might not in the future.

Different parts of modern cryptography rely on different sets of hypotheses. Eg the discrete logarithm problem being hard for some specific groups is one popular hypothesis.

> In theory, yes, in practice, there is a pretty big difference [...]

That's a valid point, but to make that point the approach you defend has to be more mathematically rigorous.

Basically, if you say '(I am just testing a new algorithm)', then that algorithm better be fast in order to convince anyone. Otherwise, you say something like 'I'm working on a proof for my new approach.' or 'I'm working proving sub-exponential runtime for a new algorithm'.

Ideally, if you don't want to be a crackpot, it helps to be well versed with the literature, and what has been done before and why it does or doesn't work.

(The former is especially important, if you want to claim you have a new proof for P != NP, because researchers have already formally ruled out lots of different approaches; so you better be able to explain why your approach does not fall under any of the ones that have already been proven not to work.)

[js8]

> Oh, that's not what I meant to say at all.

I see. I didn't really wanted to claim anything (or much) in this respect. I am working on a "candidate algorithm", that I believe could be in P with low degree (o(n^8)). (And if it's not in P, I think it will be very useful to understand WHY it is not; that's one of several reasons why I am testing it.) The reasons why I believe it's in P are complicated (I would have to describe the method), and I didn't wanted to go into that. Still, that's why people should take P=NP as a real possibility.

AFAICT my approach is novel, but if some expert genuinely wants to help me understand where it is not novel, I will gladly explain how it works.

[eru]

OK, that sounds a lot more reasonable.

I'm assuming you are working on solving some NP-hard problem?

> And if it's not in P, I think it will be very useful to understand WHY it is not; [...]

Yes, that's a good approach!

Btw, I spent quite a few years on and off trying to resolve the following question https://cstheory.stackexchange.com/questions/41251/simulate-... "Can you 'simulate' a heap in linear time?"

I would have been equally happy to find an algorithm that works in linear time, or to prove that it's not possible.

Last year I finally found the linear time algorithm.

> AFAICT my approach is novel, but if some expert genuinely wants to help me understand where it is not novel, I will gladly explain how it works.

I'd be happy to take a look.

[js8]

> I'm assuming you are working on solving some NP-hard problem?

Yes, my choice of the problem is 2XSAT, which is a SAT class whose instances have clauses from 2-SAT and XORSAT. I proved (and I think that's where it becomes novel) that this class is NP-complete. This leads me to believe there is a clever generalization of polynomial algorithms for 2-SAT and XORSAT, and that's the subject of my interest.

The trouble is, algorithms for 2-SAT and XORSAT are wildly different. My first attempt to unify them, half a year ago, has failed. Since then I have made a lot of progress on the theory; now I have another candidate algorithm which generalizes them, and I am about to test it.

> Yes, that's a good approach!

I know, but it gets even better. I roughly follow what Krom did with 2-SAT in 1967. And it turns out, even if your attempt at polynomial algorithm turns out to be incorrect, the character of the exponential blow-up gives you at least some hint of what you need to fix.

> I'd be happy to take a look.

I wish I had written more on it, but the research got priority. For two months now, I am sitting on blogpost draft that outlines 2/3 of my strategy, as well as half of a proper paper; I was waiting if I can somehow conclude with a candidate algorithm, but I don't really have yet that written down in a formal way (it's new so some understanding needs to happen). I'll probably publish the blogpost as it is, and the actual algorithm (if the test implementation works out reasonably well) later as another blogpost. If you're still interested, I will send you an email when I publish the first part, probably this weekend, and you can tell me what you think.

[eru]

Yes, I'm interested. There's an email address in my profile here.

My academic background is more on linear optimisation (and integer and combinatorial optimisation), but looking more into the various flavours of SAT would also be interesting.