Guuber's blog

I need codes with non-obvious time complexities for testing gpt-3 / codex abilities
By Guuber, history, 3 years ago, In English

I have been playing lately with the programming abilities of Codex and one thing that surprised me was how accurately it figured out the time complexities of the codes. I have only tested with about 10-20 competitive programming codes and it has deduced the time complexities correctly in every of them. Most of the codes were pretty simple / standard, so I got curious of how "complicated" codes it could guess the time complexity correctly. My intuition is that it could be hard to interpret the time complexity from recursion with a non-trivial base case but I haven't yet tested this too much.

So my challenge for you is to create program(s) from which Codex can't "guess" the time complexity correctly and posting the code as a comment below.

By guessing I mean that I give the code + a line like "// The time complexity of the algorithm is " and let the codex fill out the rest (usually the time complexity in big O notation)

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Have you tried Manacher's algorithm for finding palindromes? Or anything else where you have nested loops but the inner one just forwards another index $$$j$$$ and never resets it when going from $$$i$$$ to $$$i+1$$$? Maybe try algorithms where one would talk about amortized complexity?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I have now tested with one code with nested loops such that the inner one forwards to another index and it did not get that one right. Even though it sometimes explained that there is a window that is sliding (I'm not sure if it's called a sliding window if the size changes) but it still didn't get the time complexity right.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Have you tried Hopcroft-Karp, Dinic's, and Mincost Maxflow algorithms? They're all relatively famous for having hard-to-guess complexities. Also Splay trees, minimum queue/stack, dsu, etc.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Thanks for the suggestions! I copied some implementations of these algorithms from internet and gave them to GPT-3. The problem is that it recognized the algorithms and because of that it probably "knew" the time complexity was without actually "deducing" it from the code. One thing I could try would be to implement the algorithms myself (or then just try to modify the already implemented codes such that it's harder to recognize them). But I think that it might be also a problem in self implemented code that it recognizes the algorithm (it can pretty well recognize what is the "point" of the algorithm when I give it only the code). I think that most efficient would maybe just to write own algorithms that are designed to be a little more difficult to interpret time complexity. This way it would also be possible to alter the difficulty.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You can try my treap. It's e-maxx based implementation but with enough of my variations that it shouldn't be instantly recognisable.

      If it can't handle class templates (with some code that uses it, like update/query) in general, then that's one category.

      → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How does your GPT-3 model deduce the time complexity of the code? I thought it is an auto autoregressive rather than an autoencoder one? Could you share the architecture?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Now that I think about it more, "deduce" is not really the right word. What I meant by it is that it can tell me the time complexity when I give it the code and comment like

    "// The time complexity of the code is "

    and then it fills out the rest (usually the next word is the time complexity using Big O notation).

    While writing this reply I realized that I am using Codex and not GPT-3.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Guuber (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Try implementing a Link-Cut Tree but instead of Splay use a join-based Treap as the base data structure? IIRC the total complexity of Link-Cut Tree can be amortized to a simple $$$O(\log n)$$$ with Splay, but cannot do so with a Treap, rendering it $$$O(\log^2 n)$$$.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If you're just trying to trick it, there are a couple things that'll probably get it:

1) Write any moderately-complex dp recursive DP, but forget to set your memo (or forget to read it). Then your code is exponential. This is an easy one for humans to mess up often.

2) Number 7 on this list. It's very non-obvious that some of these DPs are n^2 unless you've seen something like this before (which, to be fair, codex has, but I'd still expect it to get it wrong).

3) Counting the number of triangles/squares in a graph naively can be n^1.5 despite being several nested for loops. Super surprising to analyze.

Here's some psuedocode
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I copied the pseudo code from the 2) and it at first got the time complexity of O(n^2) but when I rephrased the wording it outputted O(n^3) so it might be just luck. For the 3) it "knew" that the question was about counting triangles but still said that the time complexity is O(n^2). So it seems that these problems were a bit too complex for it (not too surprising).

    → Reply