> the extended thesis it depends on is "No physical procedure can decide an NP-complete problem in polynomially many steps."

I think part of the confusion here, is that usually the extended church turing thesis means that any physical computation can be efficiently (in polynomial time) simulated by a deterministic turing machine. (And thus if quantum computers exist and BQP is a superset of P, the proposition is false). I've never seen it defined before as above. But im definitely not a complexity theorists.

But remember that "efficient" in terms of P and NP is about scaling. P == NP doesn't necessarily mean that a practically efficient algorithm can be found. The polynomial exponents involved may be large: O(N^1000) does eventually scale better than O(e^N), but that doesn't mean it is practically useful!

This is pretty unrelated to the topic at hand, but people say that as if its a cop out answer to the conundrum, however i think it would be both the most intersting and most unlikely outcome to the whole p vs np saga. Possibly even more crazy than the answer being uncomputable.

Think about what that would mean. It essentially amounts to a loop nested 1000 times would be enough. 1001 tumes is more than needed, 999 times is enough. Having high transition points like that in math is super rare and interesting. Things are usually either a small number or infinity; almost never a large number. Like i can't think of any non contrived polynomial time problems you would actually want to solve that are worse than n^20, let alone n^100 (excluding cheating by fixing one of the parameters as part of the problem). I don't know what such a result would mean but it would be fascinating.

Assuming X is true, that implies Y. We don't think Y is true therefore we now doubt that X is true, is a very standard thing to do in math.

Yes, but the title suggests that "[method] solves NP-complete problems", and sounds kind of like "Quantum-Physics-related trick solves NP-complete problems".

Moreover - it doesn't even solve NPC problems conditionally, but that show that "in principle" they should be / would be solvable.

I'm not sure i think those situations are comparable. If a rust func is taking an Option<t>, its essentially advertising that it can handle None values. That feels quite a bit different from giving a c function a null pointer and having it freak out.

Ye, sure, but Rust won’t compile a `foo(std::ptr::null())`, if the function is defined as `fn foo(b: &Baz)`. C doesn’t get that luxury. That is the point of the article.

  $ gcc -Wall -Werror -x c - << EOF
  void f(int x[static 1]){}int main(){f(0);}
  EOF
  <stdin>:1:37: error: null passed to a
      callee that requires a non-null argument
      [-Werror,-Wnonnull]
    1 | void f(int x[static 1]){}int main(){f(0);}
      |                                     ^ ~
  <stdin>:1:12: note: callee declares array
      parameter as static here
    1 | void f(int x[static 1]){}int main(){f(0);}
      |            ^~~~~~~~~~~
  1 error generated.

It can be done, though it usually isn't.

`int x[static 1]` isn’t exactly intuitive when one wants to define a reference to an integer. Nor is this practical given a dynamic array of integers. Or a single integer field in a struct.

Can you do that with a dynamic array? If not, it's pretty severely limited (unless you mean that literally forbidding dynamic memory is usually not done, which I guess it's true outside of some embedded code but not a particularly meaningful statement).

The syntax is rather confusing. This is not an array of length 1, but rather a pointer which points to a memory segment which is at least 1 integer long. In other words, any array of any length (>=1) would be a valid argument to this function. "static" here means "don't do the normal thing where you totally ignore the length of an array argument to a function (which is, like usual, really just a pointer)". "static" was chosen because the keyword was available rather than because it was a particularly descriptive name.

I see. Can you use `static 0` for a non-null empty array, or does that run into issues around what it means to allocate 0 bytes? I feel like the distinction between "empty but safe to use" and "not safe to use, so you need to check first" is a pretty important part of what most of the solution look like in languages that don't have this problem. Being able to statically know that something is non-empty is nice, but it's not quite the same as being forced to check if it's valid.

I can understand that this a somewhat practical solution to the problem of codebase is all C and all I have is a C compiler, so there is merit to using the static keyword here. But it is also unwieldy and used rarely, so I do not think it is comparable to Rust’s borrow rules in any meaningful sense.

> Can you do that with a dynamic array?

Yes.

  #include <stdio.h>
  
  #if __has_include(<stdcountof.h>)
  #include <stdcountof.h>
  #else
  #define countof(a) (sizeof (a) / sizeof *(a))
  #endif
  
  void
  foo(int n, int a[static 1][n])
  {
   printf("sizeof *a: %zu\n", sizeof *a);
   printf("countof *a: %zu\n", countof(*a));
  }
  
  int
  main(int argc, char *argv[])
  {
   int array[argc];
   foo(countof(array), &array);
   return 0;
  }

  $ ./foo                            
  sizeof *a: 4
  countof *a: 1
  $ ./foo 2 3
  sizeof *a: 12
  countof *a: 3

Tested using Apple clang 21.0.0 and gcc 15.2.0.

The syntax for using passed VM arrays is stilted; you're operating on a pointer to an array, which can get confusing and is error prone. Because of the semantics for array passing and need for backward compatibility it's too easy to get it wrong without the compiler catching mistakes and complaining. Though, the C2y _Countof operator is required to error when used on a non-array, so using _Countof(a) instead of _Countof(*a) will fail. (GCC and clang also have warning diagnostics that work for the fallback countof macro.) And there's no way (or no easy way?) to ask compilers to inject automatic bounds checking when operating on arrays, at least outside non-production debugging modes like ASan.

But C is getting there, slowly.

But it isn't different, that's Tony Hoare's Billion Dollar Mistake.

It's absolutely different: “I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.”

His mistake was making _all_ reference taking functions also accept null. In Rust functions opt into None | Some

This comes up with C# which must have default(T) so references default to null. In Rust there is no general default(T) that must always resolve

My contrast was to "That feels quite a bit different". The type system in C only has Tony's nullable references, you can't say that you don't mean that because it wasn't your choice to make, it's like if some C programmers say obviously they don't mean zero when they take an integer - too bad, C doesn't have the non-zero integers (Rust does, NonZeroI32 for example is the signed 32-bit integers except zero)

It seems like you're pretty fundamentally misunderstanding what the mistake is, because you have it backwards. Null is a problem because you can just use it like any other pointer without having to explicitly decide how to handle if it's null; Option does not have this problem because you have to explicitly decide how to handle if it's None. Even if you choose to crash if it's None, that's an explicit operation on an Option itself, not the underlying value. There's no equivalent way to force an explicit decision about handling null; it looks just like every other pointer, which means that the only way to avoid using it like one is to be really careful (which we have decades of empircal evidence showing might as well be impossible to do uniformly).

It is different. Handling `None` in a way that crashes your program is well defined in a Rust function. If you're using `unwrap` or `expect`, the program will crash with a stack trace and an error, instead of running into undefined behavior.

Yes. Its also explicit instead of implicit. In rust (and typescript, swift, haskell and others), you have to opt-in to nullability. By default, functions can't take a null in place of a non-nullable value. And whether a function accepts a T or an Option<T> is part of the signature.

While it is undefined behavior on the C standard level it a null pointer dereference is guaranteed to trap on most platforms.

When we are talking about one of the most used pieces of software in the world, there is always things to do.

> And it surprises - and saddens - me that not even friggin curl has the financial muscles to have somebody on-call for one month...

Is it that they can't or don't want to. I'm sure curl is popular enough that it could attract a co-maintainer if it wanted to. Of course there is a cost to that. Software projects done effectively by a single person are often more focused and designed more coherently. I'm not sure curl would be as good a product if there were multiple maintainers with potentially conflicting visions.

> Especially since it appears there is a solution if you truly need a fix.

If you ever really need anything fixed in the open source world, there is always the option of doing it yourself

Doing the fix yourself is almost always the easy part. Disclosing it and getting a patch shipped across the entire Internet is the hard part.

Why would you personally need the entire internet to receive a fix?

I'm thinking of something on the order of Heartbleed. Sure, you fix it in your own servers. Are you sure you're ok with the entire Internet being vulnerable for two months? You don't have any data stored on servers that are outside of your control?

It's handy if you run a service and the internet runs clients you didn't write to access said service. (or vice versa)

Also handy if the internet is running a DDoS reflector and you're being targetted.

Otherwise, usually no sense of urgency for fixes I did for me/my employer and want the rest of the world to benefit. My problem is solved now, everyone else can get it when it ships.

Running a fork is a lot of work. You need your fixes upstreamed so that you don't need to backport other people's fixes

For a couple months? Not a big deal

Nobody said doing it yourself was neccesarily easy. Its just an option that is there.

You don’t need to backport other people’s fixes. You only need to re-merge your patches into updated versions of the upstream (aka vendor branch), which usually is straightforward.

Maybe you mean that if there are many people like you, they’d want to integrate each other’s fixes. But then you’d probably have the combined manpower to start maintaining a true fork.

Yes - and realistically, if you're $BIGCO who's shipped a billion devices with some obscure curl vulnerability you just discovered, then the hard part is going to be rolling out a patch to all of them anyway, which is still a 'you' problem.

> restic/borg is not a backup application because you backup to a folder in the same directory called `.git`... doesn't sound right does it?

It does sound right.

Obviously the world isn't black and white, and whether something is a backup depends on what threats you are backing up against. Backing up in case of disk failure looks different then if you want your backup to survive a nuclear war.

But ultimately yes, if you configure restic/borg to backup to a different directory on the same disk (and not even different access control), that is not a backup.

> if we ignore the requests of humans who create new, useful things

The author of this tool consented when he choose a license that allowed such things. If he wasn't ok with it he should have chosen a different license. Intentionally creating booby-traps is unacceptable in all circumstances.

> They can license the code for use under almost any terms they like, including restricting how you use the code.

The open source definition requires no discrimination against fields of endeavour.

If you place restrictions like this in the license it no longer meets the definition of open source.

You can obviously license things however you want, but you cant also claim its open source.

This has the same energy as, technically officer, i didn't shoot him, i just aimed at him and pulled the trigger. After that point the bullet just did its thing. Go blame the bullet.

When it comes to responsibility, usually we consider a person intentionally doing something that they reasonably believe will have some consequence as responsible for that consequence. Especially when the primary reason they took the action was to generate the consequence. Excuces of the form "Technically i didn't do it, i just knowingly did something for the explicit purpose of triggering some downstream consequence" generally do not fly.