I think that when a design problem is impossible, there is often an argument for why it’s impossible. Certainly that’s not obvious though, and you might just be out of luck. (That said, it’s also not obvious that problems in NP are easier to solve than Σ2P, both contain problems you just can’t solve and so you are relying on extra structural facts in either case.)
I think that when a design problem is impossible, there is often an argument for why it’s impossible.
My knowledge/experience is limited but I know in cryptography we generally can’t find arguments for why it’s impossible to design an algorithm to break a cipher, and have to rely
on the fact that lots of smart people have tried to attack a cipher and nobody has succeeded. (Sometimes we can have a “security proof” in the sense of a reduction from the security of a cipher to a problem like factoring, but then we’re still relying on the fact that lots of smart people have tried to design faster factoring algorithms and nobody has succeeded.) Note that this is only a Π1P or co-NP problem, whereas determining that aligned AI is impossible is in Π2P according to my analysis.
That said, it’s also not obvious that problems in NP are easier to solve than Σ2P, both contain problems you just can’t solve and so you are relying on extra structural facts in either case.
I guess that may be true in a raw compute sense, but there’s also an issue of how do you convince people that you’ve solved a problem? Again in crypto,
NP problems (find a flaw in a cipher) get solved by individual researchers,
co-NP problems (determine a cipher is secure) is “solved” by people trying and failing to break a cipher,
Σ2P problems (design a fast cipher free from security flaws) get solved by government-sponsored contests that the whole field participates in, and
Π2P problems (determine that any cipher faster than X can’t be secure) are left unsolved. (The fact that people tried and failed to design a secure cipher faster than X is really weak evidence that it’s impossible and of course nobody knows how to prove anything like this.)
I think that when a design problem is impossible, there is often an argument for why it’s impossible. Certainly that’s not obvious though, and you might just be out of luck. (That said, it’s also not obvious that problems in NP are easier to solve than Σ2P, both contain problems you just can’t solve and so you are relying on extra structural facts in either case.)
My knowledge/experience is limited but I know in cryptography we generally can’t find arguments for why it’s impossible to design an algorithm to break a cipher, and have to rely on the fact that lots of smart people have tried to attack a cipher and nobody has succeeded. (Sometimes we can have a “security proof” in the sense of a reduction from the security of a cipher to a problem like factoring, but then we’re still relying on the fact that lots of smart people have tried to design faster factoring algorithms and nobody has succeeded.) Note that this is only a Π1P or co-NP problem, whereas determining that aligned AI is impossible is in Π2P according to my analysis.
I guess that may be true in a raw compute sense, but there’s also an issue of how do you convince people that you’ve solved a problem? Again in crypto,
NP problems (find a flaw in a cipher) get solved by individual researchers,
co-NP problems (determine a cipher is secure) is “solved” by people trying and failing to break a cipher,
Σ2P problems (design a fast cipher free from security flaws) get solved by government-sponsored contests that the whole field participates in, and
Π2P problems (determine that any cipher faster than X can’t be secure) are left unsolved. (The fact that people tried and failed to design a secure cipher faster than X is really weak evidence that it’s impossible and of course nobody knows how to prove anything like this.)