4 ms·
No, it's a dumb mistake, I was thinking of the number of subgraphs of the N-node graph. I'll fix it.
by hwayne 3y ago
No, it's a dumb mistake, I was thinking of the number of subgraphs of the N-node graph. I'll fix it.
- klyrs 3y agoI'm not sure you want subgraphs, either. Succinct circuits encode exponential-sized graphs in poly space. 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.
- isaacfrond 3y agoI'm not sure the new formulation is correct either. It now states. An n-node simple graph (...) then we can encode the graph in polynomial space! But any n-node graph can be encoded in polynomial space. Maybe you mean to encode a 2^n node graph in polynomial space?