# Is asking for a bounded time complexity allowed?

Say, if someone asks for a code-golf like this:

# Test primality under polynomial time

Given a positive integer, test whether it is prime.

## Rules

• The algorithm must have polynomial time complexity in respect to the number of digits of the input.

• The algorithm must be deterministic.

• Input type and format doesn't matter, but it must be able to represent arbitrary-length integers. In Haskell. Integer is an example. In C++, since it doesn't natively support arbitrary-length integers, std::string with ASCII digits would be acceptable.

• If the input isn't a positive integer, it falls in don't care situation.

This will force everyone to implement AKS Primality Test, if their language doesn't have a builtin for it. Can such thing be accepted?

• Yup, check out the restricted complexity tag: codegolf.stackexchange.com/questions/tagged/… – xnor Feb 10 '20 at 10:29
• Just as a note, be careful when doing this - you'll likely get some invalid submissions. Further, you might not get many solutions, since answers will essentially have to prove they meet the requirement. I think most users will tend to implement a known algorithm rather than do something original. None of that makes this bad - just some stuff I think is worth knowing. – FryAmTheEggman Feb 10 '20 at 19:22
• The AKS algorithm is not particularly hard to implement - the wikipedia page makes it look very doable. I think the hard part was the proof of its optimality, not the implementation. – isaacg Feb 10 '20 at 20:38