I am currently working on a puzzle game. I am aiming in the future to ask a publisher to publish it. What do you think could be the minimum viable product to reach before sending it. I am talking about the completeness of the work (number of levels, graphic details etc)
The completeness of the work depends on the publisher, the game, you and the relationship you have with that publisher.
Each publisher will have their own standards for what's complete enough. Further, those standards could be tighter or less restrictive depending on the relationship you have with them. If you've never spoken to them, and they don't know you, it's likely you'll need something a bit more complete than if you were taking another game to them after you'd already had one success with them.
And it depends on the game. If it's mostly complete, but critical/technically challenging components are missing, that's more risk to the publisher. The genre is also important, if your puzzle game is mostly complete, but adding additional levels is very difficult or has the potential to break other things, that's more risk to the publisher.
Additionally, it depends on you and what you've produced before. If you have a portfolio of completed games, the publisher may feel more comfortable accepting something that isn't entirely complete, because they "know you're good for it".
This situation is like a job interview. If you can convince them you can do the job, and you'll do it well, they're more likely to hire you.
Your job is to convince them that the risk of taking your game is low. You can do that either by proving that the game is complete enough to be of very low risk on its own, or that the work that still needs to be done can be completed easily by you.
Your sales skills will come into play here. You need to sell yourself along with the game. If the game is incomplete, this increases the importance of selling yourself. If the game is totally done, this reduces the importance of selling yourself. It's up to you to decide how well you'll sell, and therefore how complete the game needs to be.
Depends on the publisher, really. Some of them want to see polished almost finished products, others want to be involved as early as possible in the process.
You can probably just ask them. It's possible that they may take a look at your early demo and give you some feedback or advice "for free" (e.g. without you having to make a commitment to publish with them, for example).