4 ms·

> I am philosophically very close to finitism, and I think from the perspective of the Skolem's paradox it's not clear whether different infinities are not just

> I am philosophically very close to finitism, and I think from the perspective of the Skolem's paradox it's not clear whether different infinities are not just a "mirage", so to speak. The distinction between finite and infinite seems to be much more "real" to me. I think I'm also in the same camp (finitism). My view is that infinities are kind of "verbs" rather than "nouns", even if we use them as if they were nouns for short-hand. I guess another way to say that is infinities have algorithms associated with them, where we kind of "turn the crank" and get more output. > And as I describe in that other thread, with the 2XSAT being NP-complete, the idea that you have two finite sets in Z_2^n that are each relatively easy to describe (instance of 2SAT and instance of XORSAT), but their intersection (which is in 2XSAT) is somehow "difficult" to describe is just.. really really hard to take seriously. Of course it's just another intuition, but I don't see how anybody who believes that P!=NP can look at this and not start doubting it. I don't understand the hesitation here. Once you have a fundamental gate (NOR, NAND, etc.) you have universal computation. In my opinion, 2-SAT is just barely in P because of the extraordinary restriction that each clause have 2 variables. As soon as you relax that condition, it's easy to do arbitrary computation. > ... if you assume P!=NP, then you believe that progressing this way is essentially impossible. I think we're in agreement here. My personal view is that it's not so much better to assume P=NP as it is to understand that there are different ensembles of problem space to choose from and even if the larger "space" is NP-Complete, the ensemble might only produce "almost sure" polynomial solvable instances. This is the case for Hamiltonian Cycle problems on Erdos-Renyi random graphs, for example. > ... then you're not constrained with natural proof limitations and there is no reason for hopelessness. I do wish I understood the natural proof limitation a bit better. I suspect there's a loophole somewhere or, at the very least, pointing us to another region of proof technique, but I just don't understand it well enough to know what's going on. > ... now I am tilted to believe that P=NP and there is actually an efficient algorithm ... I guess I don't have much hope of convincing you otherwise but I would like to point out again the "finite Halting Problem" interpretation. For an arbitrary program F(inp,K) (input `inp` and runs for K steps as a parameter), you're saying that the following can effectively be short circuited from an exponential search to a polynomial one: for inp in [0 .. 2^{n-1}] do if F(inp,K) then return true done return false To my eyes, if this can be short-circuited, it's essentially saying that for arbitrary functions, there's no actual reason to do computation as it can be short-circuited. In other words, you're saying one can do better than raw simulation in every single case. While potentially true, it seems like a pretty bold statement.

js8 3y ago
> In my opinion, 2-SAT is just barely in P because of the extraordinary restriction that each clause have 2 variables. As soon as you relax that condition, it's easy to do arbitrary computation. I think your intuition is wrong here. The number of variables in the clause is not the reason why NP is difficult. XORSAT also has arbitrary number of variables per clauses, and is doable in P. Furthermore, the 2XSAT reduction shows that you can represent any 3-SAT clause only with 2-SAT and XORSAT clauses. > To my eyes, if this can be short-circuited, it's essentially saying that for arbitrary functions, there's no actual reason to do computation as it can be short-circuited. In other words, you're saying one can do better than raw simulation in every single case. While potentially true, it seems like a pretty bold statement. I don't think that's what P=NP would imply. Remember, if P=NP, the algorithm is polynomial in the worst case, it can still be true that for a portion (even a majority) of actual instances, the simulation is faster than applying the algorithm. (Also it's possible that for some instances, functions that already have been properly "inverted", the decision algorithm and the simulation are equivalent, this is similar to linear equations, once you have factorized the matrix to the upper echelon form, then application of the matrix is the same process as solving it.) What the result will say that you don't need to be exponential in the worst case.
- abetusk 3y ago
  > I think your intuition is wrong here. The number of variables in the clause is not the reason why NP is difficult. XORSAT also has arbitrary number of variables per clauses, and is doable in P. Furthermore, the 2XSAT reduction shows that you can represent any 3-SAT clause only with 2-SAT and XORSAT clauses. XORSAT is not NP-Complete because a chain of XOR boolean functions can't be chained to create arbitrary computation. 2SAT is restrictive because, even though it has a "fundamental" gate (NAND/NOR), the "splay" of variable interaction is so limited. In some sense, 2SAT and XORSAT, each individually, are conspiring to prevent general purpose computation. > I don't think that's what P=NP would imply. ... What the result will say that you don't need to be exponential in the worst case. If P=NP, then the program I listed above can be short circuited from exponential search to polynomial.
  - 3y ago

js8 3y ago

> In my opinion, 2-SAT is just barely in P because of the extraordinary restriction that each clause have 2 variables. As soon as you relax that condition, it's easy to do arbitrary computation. I think your intuition is wrong here. The number of variables in the clause is not the reason why NP is difficult. XORSAT also has arbitrary number of variables per clauses, and is doable in P. Furthermore, the 2XSAT reduction shows that you can represent any 3-SAT clause only with 2-SAT and XORSAT clauses. > To my eyes, if this can be short-circuited, it's essentially saying that for arbitrary functions, there's no actual reason to do computation as it can be short-circuited. In other words, you're saying one can do better than raw simulation in every single case. While potentially true, it seems like a pretty bold statement. I don't think that's what P=NP would imply. Remember, if P=NP, the algorithm is polynomial in the worst case, it can still be true that for a portion (even a majority) of actual instances, the simulation is faster than applying the algorithm. (Also it's possible that for some instances, functions that already have been properly "inverted", the decision algorithm and the simulation are equivalent, this is similar to linear equations, once you have factorized the matrix to the upper echelon form, then application of the matrix is the same process as solving it.) What the result will say that you don't need to be exponential in the worst case.

abetusk 3y ago
> I think your intuition is wrong here. The number of variables in the clause is not the reason why NP is difficult. XORSAT also has arbitrary number of variables per clauses, and is doable in P. Furthermore, the 2XSAT reduction shows that you can represent any 3-SAT clause only with 2-SAT and XORSAT clauses. XORSAT is not NP-Complete because a chain of XOR boolean functions can't be chained to create arbitrary computation. 2SAT is restrictive because, even though it has a "fundamental" gate (NAND/NOR), the "splay" of variable interaction is so limited. In some sense, 2SAT and XORSAT, each individually, are conspiring to prevent general purpose computation. > I don't think that's what P=NP would imply. ... What the result will say that you don't need to be exponential in the worst case. If P=NP, then the program I listed above can be short circuited from exponential search to polynomial.
- 3y ago