Do I have to acknowledge the company where I started a project when I later publish related research in college? I completed an internship at a company. During the internship I worked on a generic and publically well-known problem statement and delivered its solution to the company.

After the internship, I wrote a research paper under the guidance of my college professor on a similar problem statement (a kind of subset of the problem statement) with a very different solution as compared to the solution delivered during the internship. The paper was accepted at an A+ international conference. When the company got to know regarding the paper, they demanded an acknowledgment towards them in the paper.

But I feel that the only role of the company was to give me the problem statement. The paper was made possible only because of me and my professor's hard work. And the solution developed by me during the internship was also due to my skill and hard work.

So, how legitimate is the demand of an acknowledgment by the company, should anyone demand such acknowledgment in someone's work? Am I obliged to acknowledge the company in my paper? As an ethical practice I can show gratitude towards the company by mentioning in the paper that "the company gave me an opportunity to work on the statement etc". But it should be my decision that I want to or not?

What are the consequences if I don't acknowledge the company.
At least in my field, Acknowledgements are generally regarded a fairly informal mechanism. There are few rules dictating what must and mustn't go in there. However, given that mentions in the acknowledgements don't dilute formal credit, I see no reason not to be as generous, gratuitous and grateful as possible in an acknowledgements section. Its not like adding an author, it costs you nothing and makes you look like a better person. Why wouldn't you?

Also there is probably an argument that you spent time thinking and learning about the general problem domain while being supported by the company.

I recommend adding something like "The author acknowledges BigCorp PLC for first bringing the problem to the authors attention and [financial?] support for work on related approaches", to the acknowledgements.