2
\$\begingroup\$

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?

\$\endgroup\$
  • 4
    \$\begingroup\$ Yup, check out the restricted complexity tag: codegolf.stackexchange.com/questions/tagged/… \$\endgroup\$ – xnor Feb 10 at 10:29
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – FryAmTheEggman Feb 10 at 19:22
  • \$\begingroup\$ 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. \$\endgroup\$ – isaacg Feb 10 at 20:38

You must log in to answer this question.

Browse other questions tagged .