Computational Complexity: Rules vs Standards - Scholarsquare

You can write laws that are very specific, like the US tax code, or open to interpretation like the first amendment. In the literature these are known as rules and standards respectively.

In computational complexity, we generally think of complexity as bad. We want to solve problems quickly and simply. Sometimes complexity is good, if you want to hide information, generate randomness or need some friction. But mostly we want simplicity. How does simplicity guide us in setting guidance, either through rules or standards?

Rules are like a computer program. Feed in the input and get an output. Predictable and easy to compute. So why not always have tight rules?

Nobody ever gets a computer program right the first time, and the same goes for rules. Rules can be overly restrictive or have loopholes, leading to feelings of unfairness. Rules can require hoops to jump through to get things done. Rules don’t engender trust to the ones the rules apply to, like very tight requirements on how grant funds can be spent. We know that in general we can’t predict anything about how a computer program behaves, so why do we trust the rules?

A good example of a standard is that a PhD dissertation requires significant original research. Rules are things like the exact formatting requirements of a thesis, or statements like a CS thesis must contain three papers published in a specific given set of conferences.

As an administrator I like to focus on making decisions based on what’s best for my unit, as opposed to ensuring I followed every letter of every rule. Because if you live by the rules, you’ll die by the rules. People will try to use their interpretation of the rules to force your hand.

Sometimes we do need strict rules, like safety standards, especially for people unfamiliar with the equipment. Structured rules do give a complete clarity of when an action is allowed. But it also gives an excuse. Have you ever been satisfied by someone who did something you didn’t like but said “I was just following the rules”?

Even strict rules tend to have an out, like a petition to take a set of courses that don’t exactly match the requirements of a major. The petition is a standard, open to interpretation to capture what the rules don’t.

As a complexity theorist I know what programs can’t achieve, and as an administrator I see the same with rules. I prefer standards, principles over policies. Set your expectations, live by example, and trust the people, faculty, staff and students, to do the right thing and push back when they don’t. People don’t want strict rules, but they mostly act properly when they believe they are trusted and have wide latitude in their work.