Hi,
There are a lot of different factors that could lead to random restarts which is why its hard to diagnose over the internet. It is possible it is your power supply but not necessarily. You can test your power supply using a voltmeter or even a specialist power supplier tester but this might not be an option.
With regards to overheating this could certainly be an issue but if you say the pc restarts even when it has only been on for a few minutes then it does seem unlikely. I would make sure you have adequate ventilation (fans) in order to prevent this.
Another issue that does cause random restarts is faulty device drivers. I would make sure all your device drivers are up to date and the correct driver for your hardware and OS. Possibly take a close look at the graphics card driver to make sure that is correct.
I would also suggest looking at the event viewer to see if any event is logged at the time just before the computer randomly restarts. A good guide can be found at:
http://www.bleepingc...topic40108.html
Any questions feel free to ask.