51–60 of 63 posts
Earlier quoted context omitted.
P^O is always a subset of NP^O, whatever the O.
I think the gp left out the strict before the later subset statements.
P^O1 strict subset NP^O1
and
P^O2 equals NP^O2
My pure amateur, possibly muddled understanding is that P=!NP is rather different from most open conjectures. A) It's extremely general or even "foundational" in the sense that it's asking whether any algorithm at all exists to solve an extremely general sort of problem in polynomial time. B) All of the standard methods used to solve problems of this sort have at least been pronounced exhausted at this point. C) Very…
Earlier quoted context omitted.
SAT solvers are not fast on average. Even some very simple random distributions produce small (<100 variables) SAT instances that are very hard for the solvers.
Do you have a link ? I've been on the lookout for small hard SAT instances for some time and haven't really found any.
In my mind I always regard P/NP in the same category as the Riemann Hypothesis^. That has been open since 1859 (160 years) and shows no signs of cracking. So in other words we may be in for a long wait. ^Perhaps because one of the hypothesized examples of a hard problem is the factoring of multiples of large primes (though not proved NP Complete). Or perhaps because they are both extremely famous open problems.
One of the things that slows scientific progress is the lack of cross-discipline learning. Every so often you hear about someone taking an old concept from another field and applying it. Quite a few breakout companies have combined interdisciplinary knowledge into one product and made a mint. So many people are affected by NP complete problems that you'd think that someone would have a problem that appeared simpler o…
Earlier quoted context omitted.
One of the things that slows scientific progress is the lack of cross-discipline learning. Every so often you hear about someone taking an old concept from another field and applying it. Quite a few breakout companies have combined interdisciplinary knowledge into one product and made a mint. So many people are affected by NP complete problems that you'd think that someone would have a problem that appeared simpler o…
https://m.xkcd.com/664/
Of course the real bug is in some IEEE 754 quirk you forgot to consider.
Earlier quoted context omitted.
Surprisingly, a theorem being unprovable does not mean that the theorem is untrue, even if you can prove its unprovability! This was shown by Goedel ( https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... ). He showed that there exists no system powerful enough to express theorems about the natural numbers which can prove all facts about natural numbers and be sound (ie not prove things that are untrue).
That's not exactly what I'm saying. What I am saying is that it's impossible for it to be true and unprovable. If it is true, it means a proof exists. Also, I am talking about this specific problem.
Gödel's statement, which essentially says "I am unprovable" is an example of a true, unprovable statement.
Earlier quoted context omitted.
Do you have a link ? I've been on the lookout for small hard SAT instances for some time and haven't really found any.
SAT competition 2018 http://sat2018.forsyte.tuwien.ac.at/index.php had a track with random instances. The article "Generating the Uniform Random Benchmarks" in https://helda.helsinki.fi/bitstream/handle/10138/237063/sc20... contains the descriptions of the random instances used.
I'm going to download the benchmarks and try to correlate them with the results CSV table (which doesn't show number of variables for each instance), but since the full random benchmarks are 2.9 GB compressed this might take a fair amount of work.
If you can provide any further guidance on finding the relevant instances I'd appreciate it.
Earlier quoted context omitted.
When people try to use 'NP complete' as a dodge for doing difficult coding at work, I point out to them that Claude Shannon proved that generalized compression algorithms can't exist, and yet we are surrounded all day by compression algorithms. Just because the space in NP hard doesn't mean that your problem is automatically NP hard. Lots of human consumable or generated data is full of patterns that can be exploited…
>[...] I point out to them that Claude Shannon proved that generalized compression algorithms can't exist [...] What proof are you talking about?
The point is that the input to your compression is not an arbitrary M-bit string, but some very structured thing which could have a smaller representation. Similarly, when encountering what appears to be an NP-hard problem in the wild, you might still be able to find an efficient solution by exploiting the structure of your input (NP-hardness only applies when considering all inputs).
Earlier quoted context omitted.
Do you have a link ? I've been on the lookout for small hard SAT instances for some time and haven't really found any.
SAT competition 2018 http://sat2018.forsyte.tuwien.ac.at/index.php had a track with random instances. The article "Generating the Uniform Random Benchmarks" in https://helda.helsinki.fi/bitstream/handle/10138/237063/sc20... contains the descriptions of the random instances used.
For example I see some instances here with 120 variables but they are 7-SAT with around 10k clauses. Unless I'm mistaken reducing those to <=3-SAT will require adding about 20k more variables and tripling the number of clauses.