I know "code is data", but it's a couple orders of magnitude more reasonable to have unsafe bytecode than to have unsafe data deserialization.
If something is supposed to load arbitrary code, not just data, that needs to be super clear at a glance. If it comes across as a data library, but allows takeover, you have a problem. Especially if there isn't a similar data-only function/library.
We don't know that factorization is NP-complete> Show me a reduction from SAT to factorization.
It's kind of trivial to say it's in NP because we can verify in P time, that's not a criticism of you just of the definition!!
I think a better definition of NP is "only nonpoly algos can exist, no P algos can exist". By that definition of NP, we don't even know that it's in NP strictly because there could exist P algorithms for solving it. It's more in 'unknown-NP' if that were a class! hahaha! :)
I think this what alot of people get wrong. "N' in NP does not stand for "not" it stands for "non-deterministic". Meaning you can solve in P time with a non-deterministic Turing machine, or alternatively, a function executing on all inputs in parallel.
> or alternatively, a function executing on all inputs in parallel.
I like to explain non-determinism in terms of getting a hint, or having an (untrusted) cheatsheet in a test. Or always making lucky guesses (but you don't trust your guesses).
But as long as your parallel executions don't interact at all, the definitions are identical, I think.
> We don't know that factorization is NP-complete.
Yes? No one ever said it was.
None of the common cryptographic problems are expected to be NP-complete, even if they aren't in P. That's because they are known to be in both NP and in co-NP, and it's expected that NP != co-NP.
> I think a better definition of NP is "only nonpoly algos can exist, no P algos can exist".
In what sense is that a 'better' definition than the standard definition? It sounds like what you are talking about is NP\P (where \ is set subtraction, ie 'NP minus P').
I think some people have asked whether it was. I'm not saying you did, just thought it was interesting! Haha :)
I don't even know what co-NP is. Could you explain?
I think that's a better definition because I find it more predictive and useful to think about: pretty concrete to know that you can't have a polytime algo for it.
Yeah, I guess what you're saying about NP\P is right in that it's a restatement of the definition of what I said, haha! I'm not an expert this is just what I think :)
> I think that's a better definition because I find it more predictive and useful to think about: pretty concrete to know that you can't have a polytime algo for it.
Well, that's a non-standard definition for NP, and you would have a hard time talking to anyone. And at the moment we have no clue whether your 'NP' has any problems in it at at all, or whether it's an empty set. In that sense, it's a very impractical definition.
Btw, there's some nice alternative but equivalent definitions for traditional NP. The classic definition is basically, NP are those problem that you can check in polynomial time if someone gives you a hint (ie they give you the answer and whatever else you need, but you need to verify, you can't trust the hint.)
A nice alternative definition says that with access to randomness, that hint needs to be at most O(log n) long, and you also only need to even look at 3 randomly chosen bits of that short hint, and you are still guaranteed to suss out any fake answer with at least 66% probability. See https://en.wikipedia.org/wiki/PCP_theorem
Thanks for the alt NP definition. I'd be fine to talk to people we just have to clarify the definitions first. Haha! :) I think mine's good but I get if you differ, no worries.
It's actually a very fascinating definition and question: Are there problems for which we can prove they are in NP but also prove they cannot have polynomial time (P time) solutions?
I did check out that wiki page first, but found it super difficult to parse. Do you have some insight that could help me understand more simply/intuitively??
For instance, I found the definition of NP as P if you have an NFA, to be super easy to understand. But when that wiki starts talking about "certificates" I just have no idea.
That is, co-NP is the set of decision problems where there exists a polynomial
{\displaystyle p(n)} and a polynomial-time bounded Turing machine M such that for every instance x, x is a no-instance if and only if: for some possible certificate c of length bounded by {\displaystyle p(n)}, the Turing machine M accepts the pair (x, c).
> Are there problems for which we can prove they are in NP but also prove they cannot have polynomial time (P time) solutions?
That's exactly the famous P!=NP question.
> I did check out that wiki page first, but found it super difficult to parse. Do you have some insight that could help me understand more simply/intuitively??
Scott Aaronson might have some good intro material on his blog. Otherwise, you can just ask your favourite search engine (or AI bot) for some intro material.
> For instance, I found the definition of NP as P if you have an NFA, to be super easy to understand. But when that wiki starts talking about "certificates" I just have no idea.
The certificate is the 'cheatsheet' or 'hint'. Basically the question is, how well can you do in an exam where you have to show your work, if someone gives you all the answers? (But that guy is a troll, so you can't trust him, and still need to verify everything.)
Cool, thank you. Yeah that makes sense. I didn't expect you to actually explain the entire thing, I just wondered if you had some, you know, insight. It's all good hahaha! :) I like your cheatsheet, I guess that applies to your previos definition of co-NP ! :)
I always found that part odd. I’d assume you would want the problem you build your crypto system built around to be NP-complete, since that would seem to put you on the firmest possible ground. And yet those are most likely not NP-complete, and I think the post-quantum systems proposed aren’t NP complete either.
Maybe being NP-complete isn’t as important as I realize? Or maybe there’s something about NP-complete problems that make them less amenable to be a valid crypto system?
> Or maybe there’s something about NP-complete problems that make them less amenable to be a valid crypto system?
To simplify a bit, the problem is that to work as a crypto system your particular problems needs to be both in NP and in co-NP. And we know of no problem that is both NP-complete and in co-NP. It's widely conjectured that there is no such problem. See https://en.wikipedia.org/wiki/Co-NP that page even mentions integer factorisation.
That's why you can't just take the NP-complete problem itself as a basis for your cryptosystem, you have to pick some subset of instances that's also in co-NP. And apparently it's almost impossible for us to pick such a subset, but still have the instances be hard enough to solve on average.
It is just an standard eUICC card with an issuer certificate, which means you need issuer's app to access low-level eUICC functions on a rootless Android. This is how esim.me enforces the subscription.
This also means, you can use any LPA implementation to manage and install profiles on your own!
It usually needs to be priv-app installed, which means you have to build it in with the rom or add it with a Magisk module (don't use the one on github though it's horribly out of date, if you must... make sure your device is in light theme mode or you won't see the QR code and confirm buttons).
I can confirm esim.me works for it, it's just expensive for one of them. This service does not require an IMEI pairing to the EID because at least in the US it's using T-Mobile (at&t has a device whitelist and verizon requires a valid IMEI/EID in their database).
That's interesting cause on a a bigger german website we are trying to figure out how to get that firsty thing working with removable eUICCs since Feb the 16th. The only person that reported there that eSIM.me is working for them used a smartphone with a built-in eUICC for "looking at the app and receiving activation code" and after that put in the eSIM.me into a Galaxy S10.
Everybody else that wrote something about working or not working — no matter if they use products from eSIM.me, 5ber or sysmocom — wrote that it isn't working for them. Even when installing the profile with the static activation code from within the APK — that can be found when using apktool on the APK and a bit of grep — I wasn't able to get a data connection with the profile deployed to the sysmoEUICC1-C2G.
Btw. firsty seems to use Vodafone here.
However, firsty support answered today that they "are looking into support for these use cases, so stay tuned!"
Definitely not the best, but the most mathematical fiction book might go to Surreal Numbers: How Two Ex-Students Turned On to Pure Mathematics and Found Total Happiness by of course no other than Donald Knuth.
And you could put The Part-Time Parliament by Leslie Lamport near that if you stretch it.
I gave Apple Map a second chance after hearing good things about it recently.
But it gave me a route where I need to turn left right after taking a right-turn ramp, except that the left turning line are separated by road dividers before the exit of the ramp. So I would need to either go wrong direction and do a 180, or bulldoze the dividers. As a comparison, Google Map never gave me that route in the past.
This happened in a moderately sized town so I guess I will still stick to Google Map for now.
