# Why does it matter how difficult a proof is?

I am confused by how the objective worth of CS theory research is assessed.

In the last year, I had been working on formalizing some tasks from a different research field in cs theoretic terms, i.e. providing proper definitions, proving bounds etc. In the end, I came up with two proper theorems that are relevant in my research field. Let's call them $$A$$ and $$B$$.

That Theorem $$A$$ should hold is quite intuitive, yet my rigorous proof involves several presumably non-trivial steps. Theorem $$B$$ is relevant for the field, but follows trivially from the definitions.

When I presented my preliminary results to some acquaintances who were knowledgeable in CS theory, they praised result $$A$$ and paid little attention to $$B$$, making the comment But this is trivial. In fact, I had the impression that they didn't read much besides definitions, lemmas, theorems and proofs.

Later, I distilled $$A$$ and $$B$$ into two seperate papers, because they were quite different. I submitted both paper to the same journal, and the paper about $$A$$ was quickly accepted, whereas the paper about $$B$$ was rejected with the comment All described results follow trivially from definition 2.

So, my question is the following: Why does it matter in CS theory how difficult the proof of a theorem is? As a domain expert, I can say that $$A$$ and $$B$$ are equally relevant to my field. Of course, $$B$$ follows trivially from the definitions, and most theorists could have quickly solved that -- but as far as I know, nobody did. Arguably, the main contribution for $$B$$ was the definition that implied the theorem--which, by the way, was quite hard to come up with--but nobody seemed to care about that.

• Was it a general venue or a venue specialized in your domain? If the scope of the venue is too general, then you may end up with reviewers that are not familiar with the internals of your domain and it will be easier for them to judge the complexity of the proofs than the relevance of the results. It is also important to stress it in your introduction and to insist on why, despite the simple proof, it is a contribution (by e.g., comparing with previous work, stressing why a definition is more than it seems etc.).
– holf
Feb 21 at 13:21
• @mto_19 This is not an answer to your question, but usually a good way to show that Theorem B is useful despite being trivial to prove is to use it to prove nontrivial things. I don't mind a culture that 'forces' people to give evidence that what they claim is important is in fact important. Feb 21 at 15:16
• I think if you replace "difficult" with "interesting" you will understand your question better. People want to read something interesting, using an idea or two they haven't seen or thought before. Ideas/proofs that look trivial at first can definitely lead to something interesting; these are not the same notion. If a theorem is immediate from a definition then it's perhaps not very interesting, the definition is what's potentially interesting. Maybe there are more theorems like this you can derive from your definition, which you can use to point back to the interestingness of the definition. Feb 21 at 18:58
• I've found many reviewers at TCS jealous. They cannot accept that one comes up with easy solutions for interesting problems, so they tend to reject by providing most nonsense responses. On the other hand, if you already made a big name for yourself or have a good network supporting you, then you can publish your simple proofs in top conferences and journals and then people will call it "elegant"! If anyone disagrees, I can show simple proofs that were already known (at least the idea) or are even wrong but accepted in top venues when they are written by so-called top researchers in the field. Feb 23 at 8:47
• @saeed I agree with you. Feb 23 at 21:26