What's worse: being mechalel Shabbos, or keeping Shabbos but not believing it is a Divine commandment? The Ramban explains "Arur asher lo yakim es haTorah hazos" (27:26) to mean that a Jew must believe in his/her heart that mitzvos are a Divine truth and believe that G-d rewards their observance and punishes their desecration. One who disbelieves is subjected to the curse of "Arur...". However, says the Ramban, if a person simply violates commandments, e.g. a person who eats pig or does not observe sukkah or lulav, but still believes they are true and that ultimately there is reward and punishment, that person is not subject to the curse in the parsha.
Of course, the fact that belief is essential is obvious from our mesorah and it seems only if your exposure to Judaism comes from the internet would you even have a hava amina otherwise (which is why the whole topic is silly), but l'ravcha d'milsa it is mefurash in Ramban.