71–80 of 101 posts
Earlier quoted context omitted.
Matrix multiplication is O(n^2.73) time and O(n^2) space. That's what eats bigger and bigger chunk of electricity nowadays.
Are there approximations? I assume it's for machine learning right?
Earlier quoted context omitted.
when proving a negativ in math, you often do a proof by contradiction precondition: Either A is true or it is false. question: is A false? solution: 1. assume that A is true 2. 3. find a contradiction 4. ==> A can not be true 5. ==> therefor A is false
In P/NP case I would need to assume that I can solve a problem in polynomial time, and then find a contradiction. To me it is really hard to see a useful path forward from there.
iirc that's actually how many of these proofs work.
> To me it is really hard to see a useful path forward from there.
yes, CS is hard.
there are resources online, that explain the general idea, e.g. [1]. But understand the specifics, you really do need a solid foundation in theoretical math and theoretical CS
[1] https://www.quora.com/What-is-a-proof-by-contradiction-in-co...
Despite having done my undergrad in CS, I never understood what NP-hard really meant. I mean yeah, polynomial time, boolean logic, general-case not specific-case, transformable into other NP problems, I get it, but like, I don't get it? Anyway, after reading this article I feel like I've gotten one small step closer to filling in this gap in my CS knowledge.
> Despite having done my undergrad in CS, I never understood what NP-hard really meant Not having done CS undergrad, I have never really understood even P/NP. The naive explanation of problems that are easy to solve and check vs problems that are difficult to solve but easy to check seems to leave something essential out. I mean, with the naive explanation you are I think you are left with either of two options: 1. A…
> I am pretty sure there is something in this problem that makes it a not legal P/NP problem
It's not in the space of P and so isn't relevant to the problem, if I'm reading your post right, as it's exponential complexity
Earlier quoted context omitted.
when proving a negativ in math, you often do a proof by contradiction precondition: Either A is true or it is false. question: is A false? solution: 1. assume that A is true 2. 3. find a contradiction 4. ==> A can not be true 5. ==> therefor A is false
Proving a negation is not a proof by contradiction, that's just the proof of an (absurd) implication. Logic people actually write blog posts about this: https://math.andrej.com/2010/03/29/proof-of-negation-and-pro...
I am glad to learn, that I just as dumb as the average mathematician lol.
> Proving a negation is not a proof by contradiction
did I say that it is, though?
Isn't there some graph problem about finding cliques that is NP-hard (presumably NP-complete in the decision version) but that has an expected _constant_ time algorithm over the usual distribution of random graphs? I seem to remember the algorithm is something like "check a few samples at random, if that doesn't find what you're after then do exponential-time search" and the point is the chance that the samples don't…
If you're allowing for some error probability, then the answer is trivially yes. For example, the NP-Complete problem of "does this graph have a clique of size sqrt(n)" is trivial over G(n, 1/2) random graphs, because the answer is No with overwhelming probability (something decaying exponentially in n or n^2). So you don't have to read the input before responding. If you're referring to Las Vegas style (always corre…
Corollary: P does not mean easy. Most things that you do on the computer, you want to be O(n) or less; maybe O(n log n) or even O(n log^x n), but no slower than that. That means if you get a bigger problem, you can generally just get a proportionally bigger computer and be all set. Now, sure, there are plenty of O(n^2) problems where the n stays small enough, or you don't mind waiting or spending a ton of money on it…
Matrix multiplication is O(n^2.73) time and O(n^2) space. That's what eats bigger and bigger chunk of electricity nowadays.
Earlier quoted context omitted.
when proving a negativ in math, you often do a proof by contradiction precondition: Either A is true or it is false. question: is A false? solution: 1. assume that A is true 2. 3. find a contradiction 4. ==> A can not be true 5. ==> therefor A is false
In P/NP case I would need to assume that I can solve a problem in polynomial time, and then find a contradiction. To me it is really hard to see a useful path forward from there.
Earlier quoted context omitted.
Matrix multiplication is O(n^2.73) time and O(n^2) space. That's what eats bigger and bigger chunk of electricity nowadays.
Where does 2.73 come from?
Strassen algorithm drops it to O(n^log2(7)) = 2.8074 because it divides the process into 2x2 matrix multiplications that can be multiplied by 7 ops instead of 8. Strassen is practical algorithm.
You can still optimize and get to 2.371552 with complex trickery, but these are galactic algorithms, meaning that matrices are so big that you can't even construct them on Earth.
Earlier quoted context omitted.
Cerium is correct, we don't know if P is efficiently parallelizable. Is there a formal proof of what you're talking about that we can read?
Are you perhaps confusing P with P complete? https://www.researchgate.net/profile/Walter-Ruzzo/publicatio...
Earlier quoted context omitted.
Matrix multiplication is O(n^2.73) time and O(n^2) space. That's what eats bigger and bigger chunk of electricity nowadays.
Are there approximations? I assume it's for machine learning right?
Something to keep in mind is a lot of these matrices are sparse, though. When most of the entries are 0, specialized data structures that know this can avoid doing all of the pointless multiplication by 0 operations. This saves far more time than some kind of approximate multiplication would.