21–30 of 103 posts
How hard is computing Ramsey numbers, BTW? Is there a word for that?
I used to be excited about complexity theory, but these days I can't help but wonder, what is the practical applications of this in real engineering problems? Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics.
Much of theoretical CS is just math and has no real practical consequences. Once in a while you do encounter something useful but it’s rare.
I used to be excited about complexity theory, but these days I can't help but wonder, what is the practical applications of this in real engineering problems? Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics.
Earlier quoted context omitted.
Pretty sure "n-node" is a typo and both vertices and edges are 2ⁿ.
No, it's a dumb mistake, I was thinking of the number of subgraphs of the N-node graph. I'll fix it.
I read a little on this, and I realize I've seen examples of succinct circuits. Hash functions are a great example of poly-sized circuits that compute the edges of exponentially-large graphs (fixing the input size to the output size, for example). Want to find the edge-reversal of that graph? It'll cost ya.
Earlier quoted context omitted.
Much of theoretical CS is just math and has no real practical consequences. Once in a while you do encounter something useful but it’s rare.
Many NP-complete problems and their Harder variants are in the realm of optimization. Packing boxes in air freight 1% tighter can have millions of dollars of practical consequences per year. Communications and electrical networks depend on the Steiner tree problem. Machine shops, restaurants, etc leave money on the table when their schedules are not well-optimized. I could go on and on.
I used to be excited about complexity theory, but these days I can't help but wonder, what is the practical applications of this in real engineering problems? Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics.
There are problems we can mostly solve in polynomial time, and those gets lots of study and people talk about them a lot.
There are other problems which are equally valid np-complete problems, for example reversing most encryption and hashing algorithms (with hashes you obviously don’t get a unique reversal, but you can get something), which we generally don’t discuss, as they are entirely unsolvable in practice.
Solving Sudoku (for general sized grids) is np-complete, but usually fairly easy. Many people write quite good sudoku solvers that can solve any 9x9 in a few milliseconds.
Now, a valid sudoku is a grid which has one unique answer. What’s the smallest number of clues a valid sudoku can have?
That problem is still in a 9x9 grid, and has been solved but it up at the limit of what we can do. It took a whole bunch of clever maths, and about a million CPU hours.
Earlier quoted context omitted.
Much of theoretical CS is just math and has no real practical consequences. Once in a while you do encounter something useful but it’s rare.
Many NP-complete problems and their Harder variants are in the realm of optimization. Packing boxes in air freight 1% tighter can have millions of dollars of practical consequences per year. Communications and electrical networks depend on the Steiner tree problem. Machine shops, restaurants, etc leave money on the table when their schedules are not well-optimized. I could go on and on.
I don't think anyone doubts that. NP vs P is just talked about because its the dividing line where things first become too hard (to overgeneralize). There are lots of NP problems that are close to being tractable so it feels like they are in reach. There are also lots in this category that are things that are useful to do. While there are certainly exceptions, harder categories have problems that seem more obviously out of reach at a glance.