danbruc

But this part of the discussion is not about the article per se but the way I calculated things.

Sure, but is this unconditional?

Country A with a powerful military attacks its neighbouring country B with a weak military in order to expand its territory and gain access to resources. The population generally supports this attack, army A only attacks military targets, but army B stands no chance of repelling the attacking army and does not receive support from third parties.

In this specific situation, would we hold country B to the same standards or would we deem it acceptable if country B attacked non-military targets, civilian infrastructure, and in the extreme civilians? That does not necessarily mean that such actions would be desirable because of the resulting reaction. And there might also be higher order effects, for example a change in the understanding what is acceptable in such conflicts, that make such action undesirable in the longer term.

I have been wondering for some time if terrorism is considered acceptable in certain situations? In a David vs Goliath situation where there is no realistic chance of stopping or defeating a more powerful aggressor, would it be considered acceptable to use non-conventional means and terrorism? Or is the weaker victim expected to play by the rules of warfare and accept its eventual defeat?

The parent comment is correct, if you can count the solutions, it is easy to find a solution. Assuming there is a solution, you set the first variable to either true or false and then count the solutions. If it is zero, you made the wrong choice and the first variable must be set to the opposite value. Repeat for the remaining variables until you have fixed all of them and found a solution. This takes n invocations of the counting algorithm and is probably what the parent comment means with O(n) even though this is not correct as it is O(n times whatever the counting algorithm runtime is) and not just O(n).

But the parent comment also missed my point. They have an algorithm for the counting problem which also provides a subexponential algorithm for the decision and search problem. But they could have refuted the exponential time hypothesis with a subexponential search or decisions algorithm which would not [easily] provide a subexponential counting algorithm.

And the claimed algorithm solves the counting problem, i.e. determining the number of different solutions, which in many cases is much harder than just determining whether a solution exists or finding one of the solutions.

The start of this discussion was that I multiplied wall-clock time and number of agents and someone argued that I should not have done this. It is of course reasonable to compare how much a human gets done in a certain amount of time vs what an agent gets done in that time. But if you start increasing the number of humans or agents, you have to take that into account. Running one agent for ten seconds is not the same as running a thousand agents for ten seconds - except for the completion time - but it is comparable to running one agent for ten thousand seconds.

But the difference is always there, hiring the first guy is more difficult by the same factor as running the first agent. The relevant comparisons are between one agent and a thousand agents (original setting) and between one guys and a thousand guys (analogy). In both cases the costs will be a thousand times higher and you can achieve a thousand times more in the same amount of time, so the correct measure is time times number guys or time times number agents. The difference between adding one guy and adding one agent is irrelevant for my point and that is also pretty obvious as that crosses the boundary between original setting and analogy.

You might want to make a separate point about the cost difference of getting more done by hiring more people or running more agents, but that is a different point.

Sure, I completely agree with that, but we totally went off-topic. The questions was whether the correct measure is wall-clock time or compute-time and for that the difference in difficulty to add another agent or add another employee is irrelevant. And to reiterate my point, compute-time is what delivers the results and also is what you pay for, so that is what counts. That you can squeeze that compute-time into a shorter amount of wall-time by utilizing more resources in parallel is also important but unrelated to the fact that compute-time is what delivers the results.

No, because more agents also means more resources and hence more costs. A single agent is not the same as a thousand agents which is not the same as a million agents. You are essentially saying what can one human do with X amount of time and an infinite amount of money.

You think I could not identify all the functions in some software if I poked at it with IDA pro for 15 years? Probably depends on what exactly we are talking about, is it calc.exe or an entire office suite? But I will give you that I would probably never complete the task, I would not be willing to spend 15 years doing this. Realistically I would probably be interested in some specific functionality and identify the functions involved and ignore the vast majority.

That makes no sense, because then I could also just give the task to a million people working on it in parallel and the speed-up would disappear. You have to compare all the resources used and not pick an arbitrary one like wall-clock time because resource can often be traded for each other.

Probably and the model had access to all those results. The question is whether 500 person-years of effort would have been enough to get there from the same point that the model started. And also not any 500 person-years, not 100 mathematicians independently working on it in parallel for 5 years, but 500 tightly cooperating person-years, 20 mathematicians in the same room for 25 years.

Okay, somewhat fair point, if you have no idea how to do X and learning to do X takes a non-trivial amount of time, then using a large language model could probably get you there a million times faster in some cases. But I would want to exclude those cases because they make the speed-up meaningless and instead assume that the user is reasonably competent to do the task.

Parallelismen is not cheap, in the end it costs the same. It is one resource for a long time vs many resources for a short time.

You have to multiply them, otherwise you would also have to compare the output of a company with a single developer with the output of a company with a thousand developers, after all a company can hire an arbitrary number of developers. Running a thousand agents in parallel for one hour is the same as running a thousand agents one after another for a total of a thousand hours.