Can a PhD thesis in computer science have two major parts?
This is a question for your advisor. In general, what is acceptable in a thesis is what your advisor and committee will accept. If the division into parts makes everything clearer then all to the good. If the two parts complement one another, say theory and application, then it should be fine if the advisor agrees. 

But also, what is a "Part" is also a function of the writing style. In CS, for example, one "part" might be new and necessary algorithms and another part might be how they are applied, or evaluated, or ...

But a thesis that tries to solve two different problems is likely less useful unless they are tightly bound. In such a case, focus on one "part" and save the rest as future work.