In other words, all programs' code size by definition is length O(n).
If I take this bet, as defined, then I will win trivially.
Something's amiss.
Post by twetch#2782
I said k^n (simplified to 2^n), not k*n. The size of the in-script interpreter grows exponentially with the size of the longest script it can interpret. But I already think I jumped the gun here :x it'd be (2^k * n) for k ops which indeed is O(n)
What the chain says
- Block
- 658 161
- Time
- 2020-10-23T19:30:46Z
- Signer
- 1486QpNpWYjokSfc3DxChCQG6gS2cTvVpL
- App
- twetch
- Type
- post
- Content type
- text/plain
- Name in tx
- twetch#2782
Fields the transaction did not carry are omitted. Open the payload to see the bytes as stored.
Signed by
1486QpNpWYjokSfc3DxChCQG6gS2cTvVpL VerifiedReplies (7)
- for N ops
I need to slow down
Anyway I'll send you 10 BSV anyway if you promise to give a thorough review/analysis of this short upcoming paper
Man proving a negative is hard and not even a good goal usually
Eval+reentry (eval arbitrary code read from PUSHTX) is what could cause exponential blowup. Maybe you could do the same static analysis we do for SCALL but I shudder to think how that would look in bitcoin script...
I think you could do it at runtime with O(n^2) by examining reentry stack
Well most languages have a stack depth limit, and in any case it would be depth^2 not n^2. But yeah it gets pretty unwieldy pretty quick.
Yeah that's totally what I was thinking of but forgot when I had to explain myself mhmm