5 ms·

Well, this is somewhat heartbreaking for me. I haven't read the paper, but the result sounds very plausible to me. I am also an amateur working on P=NP. Last w

by js8 4y ago

Well, this is somewhat heartbreaking for me. I haven't read the paper, but the result sounds very plausible to me. I am also an amateur working on P=NP. Last week, I think I also proved that P=NP, but with a different method, and was about to seek publication. My result seems very similar to his, yet very different. I can prove that class of SAT which is intersection of 2SAT and XORSAT is NP-complete by reduction to 3-SAT. Then I follow the approach in Melville's Krom 1967 paper on 2-SAT, and prove that certain polynomial-sized logic (that corresponds to the intersection) is refutable complete. So you can essentially generate all formulas in that logic and if you don't find contradiction, the instance is satisfiable. I have also did some preliminary testing of my method, and was able to factor small integers with it. However, there was a bug. So, to sum up, I am not surprised that P=NP with a constructive and efficient algorithm. Take it for what you want. The future is gonna be interesting (crypto DOOMSDAY).

FartyMcFarter 4y ago
I don't understand. You said that you thought you proved P=NP, but then it turned out you hadn't. How does this help to support your belief that P=NP has been solved by someone else? Surely it wouldn't surprise you if it turns out they were as wrong as you were before? PS: Also, reducing 2SAT to 3SAT doesn't help proving that P=NP. The opposite reduction would, if you were able to do the reduction in polynomial time. But maybe I misunderstood something about what you attempted.
- js8 4y ago
  I think I have a proof, it's just not yet published. Also, the original method I was attempting contained a bug, but I understand the theory better now. So, I have some evidence, both experimental and theoretical, there is an efficient polynomial algorithm out there (and possibly many different methods). Unfortunately, not 100% verified because despite what many smartypants are saying here, it's incredibly difficult to even have a conversation about a possibility of a relatively uncomplicated proof that P=NP. (I think Millenium prize is part of the problem, but that's another discussion). And to clarify, I am reducing 3-SAT to 2XSAT, not 2-SAT. 2XSAT generalizes 2-SAT to arbitrary linear equations rather than literals (we can think of a literal as a linear equation on 1 variable). I will happily send you (or anybody) the draft I have, so that you can critique it.
  - klyrs 4y ago
    Nobody wants to read your draft about an algorithm that doesn't work. Your implementation is already giving you the critique that you need. If you get it to work and it's obviously polynomial time, you'll have something to talk about.
    - adgjlsfhk1 4y ago
      I don't think this is quite true. Most NP-hard problems are usually solvable in polynomial time, so your algorithm looking like it runs in polynomial time doesn't tell you much.
      - klyrs 4y ago
        It really depends. If you have an unbounded loop that looks like it runs in polynomial time, you're in highly questionable territory. If you have a 5-deep nest of for-loops, that's what I call "obviously polynomial time" -- if such an algorithm solves every problem you throw at it, you have hope.
        adgjlsfhk1 4y ago
        Sure, but most complicated polynomial time algorithms don't work like this. You either have cases like AKS which are obviously polynomial but not obviously correct, or cases that are obviously correct but not obviously polynomial.
        klyrs 4y ago
        Algorithms which are obviously polynomial, and non-obviously correct are the only ones I'd entertain from a novice. It's not hard to mine for counterexamples, as long as the code runs.
        js8 4y ago
        As <cat-over-keyboard> already mentioned, it's not always that simple. For example, my current approach (modeled after Krom, who doesn't even have a Wikipedia page - no wonder nobody reads him!) is a more systematic search for a polynomial algorithm - construct a polynomial sized-logic in which theories have models that are satisfying instances of SAT, and prove its refutable-completeness. This proves existence of a polynomial algorithm, because you can generate all formulas of theory (coming from SAT instance) in said logic, and if you don't find a contradiction, the instance is satisfiable. The algorithm is kinda implicit, non-deterministic, if you will (because you can generate all the formulas in any order or even generate just a subset). Anyway, my main point is - people beware, practically solvable P=NP (even for hard instances) is a very real possibility.
deleted 4y ago
[deleted]
theGnuMe 4y ago
What's your take on survey propagation? I would think that any P=NP proof would take that into account or be similar.
- js8 4y ago
  I haven't really studied it in detail, but my motivation is similar, I see SAT as a simplified version of the marginal problem, and I want to solve marginal problem (or at least approximate) because I am interested in representing knowledge intensionally. I played with propagation a lot in the past, but I don't think local propagation (that resolves conditions of a bounded number of variables at a time, until everything stabilizes) can ever work, because it would contradict Razborov result on monotone circuits. I don't remember the exact argument, but I think it would imply a polynomial monotone circuit capable of resolving the instance. Also, XORSAT is not really amenable to this either, to solve arbitrary XORSAT instance you have to add together arbitrary number of linear equations, so the number of variables per equation can balloon up. That's why more recently I focused on understanding what exactly is the role of XORSAT, and by serendipity, I stumbled upon the above-mentioned reduction (which I think is a really exciting result). XORSAT is great for testing different algorithms, because despite the fact we have a nice polynomial algorithm (Gaussian elimination), one can easily create arbitrary (and loopy) instances where propagation is difficult. The way I see it, to avoid the problems with the bound, you need to preprocess the linear equations "inherent" in the instance by adding extra variables. The exact way to add variables depends on the instance, but it can be done by solving the linear equations. Propagation algorithms that go into the process blindly, without understanding the underlying linear structure, will mysteriously fail. However, my current approach through logic, basically building up theorems about the instance, until it is decided, can be considered a generalization of the propagation approaches. The messages are true statements about variables, which are propagated by deduction rules of the logic. But this is done only after we have discerned the linear structure in the problem, which is addressed globally, as described above.
  - theGnuMe 4y ago
    That jives with my intuition. I had forgotten about the connection between Gaussian elimination and xor sat. That does sound like a good direction to reason from. How do you prevent an exponential increase in linear terms though? Good luck!

by js8 4y ago

FartyMcFarter 4y ago

I don't understand. You said that you thought you proved P=NP, but then it turned out you hadn't. How does this help to support your belief that P=NP has been solved by someone else? Surely it wouldn't surprise you if it turns out they were as wrong as you were before? PS: Also, reducing 2SAT to 3SAT doesn't help proving that P=NP. The opposite reduction would, if you were able to do the reduction in polynomial time. But maybe I misunderstood something about what you attempted.

js8 4y ago
I think I have a proof, it's just not yet published. Also, the original method I was attempting contained a bug, but I understand the theory better now. So, I have some evidence, both experimental and theoretical, there is an efficient polynomial algorithm out there (and possibly many different methods). Unfortunately, not 100% verified because despite what many smartypants are saying here, it's incredibly difficult to even have a conversation about a possibility of a relatively uncomplicated proof that P=NP. (I think Millenium prize is part of the problem, but that's another discussion). And to clarify, I am reducing 3-SAT to 2XSAT, not 2-SAT. 2XSAT generalizes 2-SAT to arbitrary linear equations rather than literals (we can think of a literal as a linear equation on 1 variable). I will happily send you (or anybody) the draft I have, so that you can critique it.
- klyrs 4y ago
  Nobody wants to read your draft about an algorithm that doesn't work. Your implementation is already giving you the critique that you need. If you get it to work and it's obviously polynomial time, you'll have something to talk about.
  - adgjlsfhk1 4y ago
    I don't think this is quite true. Most NP-hard problems are usually solvable in polynomial time, so your algorithm looking like it runs in polynomial time doesn't tell you much.
    - klyrs 4y ago
      It really depends. If you have an unbounded loop that looks like it runs in polynomial time, you're in highly questionable territory. If you have a 5-deep nest of for-loops, that's what I call "obviously polynomial time" -- if such an algorithm solves every problem you throw at it, you have hope.
      - adgjlsfhk1 4y ago
        Sure, but most complicated polynomial time algorithms don't work like this. You either have cases like AKS which are obviously polynomial but not obviously correct, or cases that are obviously correct but not obviously polynomial.
        klyrs 4y ago
        Algorithms which are obviously polynomial, and non-obviously correct are the only ones I'd entertain from a novice. It's not hard to mine for counterexamples, as long as the code runs.
      - js8 4y ago
        As <cat-over-keyboard> already mentioned, it's not always that simple. For example, my current approach (modeled after Krom, who doesn't even have a Wikipedia page - no wonder nobody reads him!) is a more systematic search for a polynomial algorithm - construct a polynomial sized-logic in which theories have models that are satisfying instances of SAT, and prove its refutable-completeness. This proves existence of a polynomial algorithm, because you can generate all formulas of theory (coming from SAT instance) in said logic, and if you don't find a contradiction, the instance is satisfiable. The algorithm is kinda implicit, non-deterministic, if you will (because you can generate all the formulas in any order or even generate just a subset). Anyway, my main point is - people beware, practically solvable P=NP (even for hard instances) is a very real possibility.

deleted 4y ago

[deleted]

theGnuMe 4y ago

What's your take on survey propagation? I would think that any P=NP proof would take that into account or be similar.

js8 4y ago
I haven't really studied it in detail, but my motivation is similar, I see SAT as a simplified version of the marginal problem, and I want to solve marginal problem (or at least approximate) because I am interested in representing knowledge intensionally. I played with propagation a lot in the past, but I don't think local propagation (that resolves conditions of a bounded number of variables at a time, until everything stabilizes) can ever work, because it would contradict Razborov result on monotone circuits. I don't remember the exact argument, but I think it would imply a polynomial monotone circuit capable of resolving the instance. Also, XORSAT is not really amenable to this either, to solve arbitrary XORSAT instance you have to add together arbitrary number of linear equations, so the number of variables per equation can balloon up. That's why more recently I focused on understanding what exactly is the role of XORSAT, and by serendipity, I stumbled upon the above-mentioned reduction (which I think is a really exciting result). XORSAT is great for testing different algorithms, because despite the fact we have a nice polynomial algorithm (Gaussian elimination), one can easily create arbitrary (and loopy) instances where propagation is difficult. The way I see it, to avoid the problems with the bound, you need to preprocess the linear equations "inherent" in the instance by adding extra variables. The exact way to add variables depends on the instance, but it can be done by solving the linear equations. Propagation algorithms that go into the process blindly, without understanding the underlying linear structure, will mysteriously fail. However, my current approach through logic, basically building up theorems about the instance, until it is decided, can be considered a generalization of the propagation approaches. The messages are true statements about variables, which are propagated by deduction rules of the logic. But this is done only after we have discerned the linear structure in the problem, which is addressed globally, as described above.
- theGnuMe 4y ago
  That jives with my intuition. I had forgotten about the connection between Gaussian elimination and xor sat. That does sound like a good direction to reason from. How do you prevent an exponential increase in linear terms though? Good luck!