1:17 AM
~$500K to study complexity theory (in UK), wow, amazing. wonder if any US grants in the field come (anywhere?) close to this.
9 hours later…
10:49 AM
@DavidRicherby I used the reply function, as I was not successful in invoking your name on chat ... some features I have not understood yet.
I have been wondering about the discussion on Difference between time complexity and computational complexity, ( cs.stackexchange.com/questions/42044 ). This is going to be a bit abstract, but my guess is that concrete example could be built. I was trying to understand whether the downvotes on answer 2 about Cyclomatic complexity were fully justified.
Taking the statement that "complexity refers to the problem, not the algorithm", it could be that a solution is expressed as a program with a size depending on one size parameter of the problem, which sometimes is the case with hardware. Then some resource (surface area, number of connection layers, ...) could well be dependent on otherwise ignored measure, such as cyclomatic complexity, or some other graph property.
11:39 AM
@babou Trying to use hardware to measure complexity is difficult because a fixed piece of hardware can only take inputs of a certain size. This means you have to define a family of pieces of hardware to deal with arbitrary input sizes. Circuit complexity uses this approach and is currently very active.
Trying to measure the complexity of problems by the length of programs required to solve them makes sense as a concept but I'm not sure it would work well in practice. Having a short program doesn't seem to correspond to our intuition about what it means for a problem to be hard to solve.
For example, consider a string S of high Kolmogorov complexity. The problem "Is my input equal to S" is computationally very easy but no short program solves it. In contrast, something like 3SAT can be solved by relatively short programs: just check all the possible assignments.
Also, short programs don't necessarily correspond to good algorithms: for example, bogosort probably has much shorter code than quicksort.
So, in this sense, I don't think that things like cyclomatic complexity have a lot to do with computational complexity because they're measuring a different thing. Of course, there might be some subtle connections that I didn't think of while writing this. But the big picture seems to be that they're aimed in different directions.
2 hours later…
2:14 PM
@babou I agree. But, typically, data is larger than programs. So if your "computer" is so resource-bounded that it can only run tiny programs, it can only run on tiny data, too. Program size can't be completely ignored, but it doesn't really fit into a world where you're measuring things asymptotically as the size of the input goes to infinity.
2 hours later…
4:03 PM
complexity of a program such as number of instructions, complexity in the code branching/ structure etc, is indeed an area of general consideration in (T)CS, but is sometimes also glossed over/ ignored. the reasons for this may be rather arbitrary. the other basic complexity areas (time/ space) turn out to be fiendishly difficult to resolve & so ignoring program complexity serves as an idealization or abstraction for now "early" in CS history. see eg powerful algorithms too complex to implement / Theoretical Computer Science — vzn 1 min ago
4:37 PM
@DavidRicherby Well, I would grant you half a point. It is true that complexity is being much abused. I complained about it in a linguistics discussion, as people were people were giving importance to asymptotic phenomena, in a context where their problems are usually very small. However, complexity is often well behaved even for small values, so that it is a proper indicator of how algorithms scale very early on.
TCS & complexity theory is not merely the study of asymptotic complexity measures. its a big part but that is one subbranch "hijacking" the overall paradigm.
@vzn This is an interesting complement.. These are clearly complexity issues. The question is whether it qualifies as computational complexity. I would think the criterion is: it is computational complexity when it can exhaust a resource.
Then, we are free to mix all kinds of resources in the computational model we choose to solve the problem, and may have complexity with regard to any of them ... provided we have some king of uniform (computable) use of all resources on a given problem size.
@vzn I did not simply upvote because I first wish to get some understanding. My feeling is that the answer is not well motivated (which I am trying to do, with my lacking knowledge of issues). On the other hand, my feeling was that the downvote (as often, especially when without explicit motivation) is more based on bias than on clear argument that it has to be wrong.
4:59 PM
5:22 PM
6:11 PM
"program size" (SAT encodings) shows up in the celebrated 2014 konev/ lisitsa erdos discrepancy proof
6:29 PM
6:55 PM
RJLipton also introduced the term galactic algorithm 2010 which is relevant. the main idea seems to be large hidden constants in the asymptotic complexity. but it can also relate to code size
> A galactic algorithm is an algorithm that is wonderful in its asymptotic behavior, but is never used to actual compute anything.
« first day (1151 days earlier) ← previous day next day → last day (3292 days later) »