What does 'substantial similarity' really mean? I got puzzled by the definition of 'substantial similarity'.

Here is the case. I dealt with two related problems, say P1 and P2, that could be treated in the same mathematical framework. I aimed to show optimal appoaches to both problems. Perhaps more details:

P1: the optimality criterion was already there (which alone was an open problem for quite a long time, like tens of years) and the tool was also ready. So I'd like to say, if one realized the criterion and the tool, the problem could be solved easily following some standard techniques. But no one recognized this before.  In the paper, we examined three different approaches, with different preprocessing before applying the basic idea.

P2: the optimality criterion was not recognized. We proved it, which turned out to be of the same sense of P1 but still different. The tool for solving this problem was also not ready, and we proved it almost from scratch (like 5 pages long), which we thought as the most significant contribution. Some discussions and applications were also involved in the paper.

We did not find a unifying theme to put the two into a page-limited conference submission, while stating related aspects in a clear manner. We also believed each had enough contributions. So we submitted two papers to the same conference. Following the conference guidelines, we tried to rephrase some common preliminary in the two papers, and cited P1 in P2 for some common issues  and also for clearly stating the contribution of P2 over P1.

However, the two papers were deemed to be 'substantially similar' to each other. I searched for what it really means and what is a criterion, but failed. So can anyone share any experience on this? Maybe I just should not submit two related works to the same conference?

Thanks.
It seems to me that they have decided, for whatever reason, that they could not justify publishing both papers. The two papers are are too 'similar', the alternate method is not sufficient to justify publishing the same result twice (and it is really hard to argue agains this even in the case where the difference between P1 and P2 is significant and offers some interesting insights). 

It may be simply poor/unclear presentation on your part or their failure to see the 'difference' you describe (Maybe you needed to `convince them' by giving explicit reasons on why both should be published, and why both methods are interesting). 

Perhaps, depending on the field and topic, they were more or exclusively interested in the 'end result' and the 'interesting' background and detail regarding P1 versus P2 was beyond their interest. 

It is possible that you could have chosen one or P1 and P2 and briefly discussed the other.