Attardo

Salvadore

Linguistic

* Bryant

Norman Holland

* Rubin

consort with the almighty evil more than once and, thereby, offered him an inexhaustible source of inspiration. Secondly, within this daring game, what does Hawthorne make of his Puritan inherited sets of values, traditions and ways of thinking? Does he mock and laugh at them? These questions will hopefully allow us to partially invalidate the theories that focus on symbolic import and do not take account of the strictly linguistic and even meta-linguistic quality of a writer's writing. To us, a more stimulating exegetic approach rests on the essence of Hawthorne's humor viewed from a vantage viewpoint that embraces all levels at once: literal, symbolic and metalinguistic.

I.

In this triple dimensional analysis 3 of Hawthorne's humor, it seems unavoidable to keep in mind Aristotle's conventional definitions of "tragedy" and "comedy" because Hawthorne's fictions may well fall into the first category exclusively if we do not pay attention to his subtle humorous fads.

Accordingly, for a writer to be qualified as a tragic writer, his work needs to deal with pathetic and pessimistic characters, doomed mankind, guilt-ridden consciences, secrets of atrocious and ineffable crimes. Not a common-sensical mind would venture calling these subjects comic or funny, or even choose them as the background for lighter and heartier thinking. Yet, if we are to believe Henning Cohen, "it is these very qualities [pessimism, egocentrism, guilt, among others] that led the authors [Cohen is speaking about Poe, Hawthorne and Melville] in the direction of comedy. 4 " Such a paradoxical claim is sure to arouse the hair of more than one Puritans had they lived to hear it. If we thus assume -and we do -that to make fun of serious and grave issues was a controversial move in Hawthorne's time, we can equally posit that it may have been in a challenging mood that Hawthorne chose to don, at times overtly, at other covertly, the disguise of humor, or, as the writer would have phrased it, the veil of humor. Surely the result is going to be explosive as the two titanic figures -Gloom and Humor -are pitted one against the other in the scramble for life.

'Surely some prodigious merrymaking is going on,' exclaimed he. 'I have laughed very little since I left home, Sir, and should be sorry to lose an opportunity. Shall we just step round the corner by that darkish house, and take our share of the fun?' ('My Kinsman, Major Molineux, pp. 14-15 5 How strange that Hawthorne should precisely at this point refer to the ongoing events as being potentially construed as "some prodigious merrymaking" when viewed from a particular vantage point 3 Which here is necessarily going to be perfunctory.

The Earnestness of Humor: Hawthorne's Puritanical Sense of Humor in "Wakefield", "Young Goodman Brown" and "My Kinsman, Major Molineux"

Linda SAHMADI, Docteur ès Etudes anglaises, chercheur indépendant

It has become a truism to say that Nathaniel Hawthorne liked to indulge himself in polarities.

Any student of our Salemite author has come across in his researches remarks of the following kind:

"Hawthorne was interested in polarities, and his writings show a keen concern for chiaroscuro effects through description and characterization1 ". It would not be exaggerated to state that claims of Hawthorne's penchant for humor have been commensurately less numerous, so much emphasis being put on his thematic concerns. Yet, numerous are his stories, whether they be short or long fiction, which are fraught with laughing heroes, smiling heroines, dark humor, or simply pithy comments. If critics have emphasized -when they had noticed itat all -this aspect it is to superimpose thematic or symbolic interpretations: innocence, Satanism, madness. This rigid typification has come to freeze their laughs into a symbolic cold which recoils the approach of warmer approaches. Without completely rejecting this reading as it is not entirely nonsensical (far from it), we would like in this essay to go beyond the surface, to look not at but through the mirror that is humor. Indeed, as we read it (or should we say "hear" it?), smiles and laughters2 in Hawthorne's fiction don't simply mean or symbolize such or such human qualities or defects. They signify, period. Hawthorne seems to be playing with humor and in this game, words are the stylistic counterpart of his mind and heart. Despite the somewhat misleading character of the title of our essay, we will not content ourselves with a Puritan(ical) justification or chastisement of the writer's humor. We will veer towards a budding meta-reading of Hawthorne's humor, according to which it is essential to see humor not as a means to achieve a symbolic or moral end, but as a means for its own sake.

To do that, we will perfunctorily confront our readings to the literal and symbolic ones which construe Hawthorne's "humor" (if they dare using the word) as implicitly related to his Puritan roots, and thus representing and symbolizing more severe, more somber considerations and thoughts. In this preliminary perspective, two questions will arise and inform our stream of thoughts. First of all, is it really possible to play with the Devil? For, indeed, Hawthorne's Puritan conscience obliged him to ("round the corner", which, in itself, deserves analysis and we will try to come back to this do-in-thesly aspect). We know, after a first reading, that what is going to unfold before Robin's very own "shrewd" eyes cannot really be qualified as a stimulating and exhilarating entertainment, at least not the same degree as Robin is expecting it. Nor should his preceding trials -humiliation, verbally violent rebuffs, quasi-starvation -can be termed "entertaining" or merry. Yet, the carnavalesque procession to come points to the comic potentialities of the whole situation. Some would rather see in this "merrymaking" the "cathartic" power that Aristotle so much praised about tragedy. Yet, this somewhat stereotyped and limited (and limiting) interpretation does not do justice to Hawthorne's prompt tendency to treat somber events in a lightly humorous way6 . How else are we supposed to read the fact that Robin would fain have "sm[itten] [the hemming old man] on the nose" if he wasn't that old? ('My Kinsman', p. 5) Unless we must see in this un-actualized violence be a most physical and literal way of being cathartically released...Which, nonetheless, would amount to recognizing Hawthorne's humoristic mood.

This seemingly clear-cut Manichaeism, more than a merely Aristotelian legacy, had been passed on to Hawthorne through generations of stern and austere Puritan ancestors who were as thunderstruck at the idea of trifling with life. They would not have felt even the slightest inclination to make merriment out of their doomed existence: "But Robin being of the household of a New England clergyman, was a good youth, as well as a shrewd one; so he resisted temptation, and fled away." ('My Kinsman', p. 10) Here, behaving as a good principled New England Puritan, Robin does not approve the impropriety of the environment, which is clearly depicted as the den of the devil. The "drowsy laughter" and "pleasant titter" surely are signs of evil temptation, destined to throw Robin into the pit of desperation and sin. Bunyan himself would have given his blessing to Robin for having resisted the alluring seductress (formerly physically impersonated by the "pretty mistress," the everlasting temptress). Surely, this trial cannot be deemed funny or humorous. There is nothing funny about being tempted by the devil or being on the brink of falling into endless despair and loss. Yet, Hawthorne seems to be turning this tragically tense event into a moment of merrymaking. This transformation, as we shall see later on, has its roots on Hawthorne's dexterous manipulation of the linguistic and stylistic materials.

Hawthorne, in a rebellious fit against his strait-laced lineage, decided to severe the entangling ties and take the forbidden road to merryland. In his case, as Cohen and others have pointed out, merriment presages gloom. As we see it, we would say that it is merriment in gloom. And this is nowhere more striking than in his dealings with the Devil. In this respect, the situations contrived by Hawthorne are not enjoying, for the characters who fall victims to this everlasting trickster, yet the author seems to feel a vicious pleasure in throwing his creatures to the big bad wolf.

' […]. The man is old, or verily -I might be tempted to turn back and smite him on the nose. Ah, Robin, Robin! even the barber's boys laugh at you, for choosing such a guide! You will be wiser in time, friend Robin.' ('My Kinsman,' p. 5)

The narrator cannot be but exasperated and completely dumbfounded by the surprisingly unwise behavior of this youth. Here, we are aware that it is Robin himself who is actually uttering these words.

Yet, this self-deprecation can certainly be identified with the deprecation by the narrator, and ultimately by Hawthorne himself. Here again, we see the brilliant linguistic and stylistic act by which the author can turn seemingly maturing thinking into another level of humor, this time donning the scathing disguise of irony, under which Hawthorne can hide to laugh at the predicament of his puppet Robin.

But we won't say more about this aspect for the moment. We just want to emphasize the annoyed tone of Robin which pinpoints the incongruity of the situation.

As Robin drew night, he saw that the passenger was a man in years, with a full periwig of grey hair […]; and at regular intervals he uttered two successive hems, of a peculiarly solemn and sepulchral intonation. [After Robin inquired after the lodging of his kinsman] [t]he citizen […] turned a long countenance upon Robin, and answered him in a tone of excessive anger and annoyance. His two sepulchral hems, however, broke into the very centre of his rebuke, with most singular effect, like a thought of the cold grave obtruding among wrathful passions. ('My Kinsman,' p. 4-5.)

More than just dramatic equipment or a characterization device, laughter in this scene (which epitomizes and sets the tone for other laughing scenes in the tale) seems to emanate not so much from the devil itself as from Hawthorne himself. The impish reaction functions as an invisible thread that links the author to his fictional world on which he bestows a distant and humorous and amused glance.

The devilish laughter is a recurring feature in most of Hawthorne's fiction and the characters endowed with such a quality (or "defect" would be more appropriate) are said to possess a devilish nature or worse, to be possessed by the devil. The louder they laugh, the more explosive it is, the more evil the heart from which it burst forth. To Hawthorne, this laughter seems to be more complicated than it sounds. It would be absurd to assign only one-sided and definitive interpretation to this godly gift (Here, we cannot but think of the psychological and psychoanalytical interpretations of Hawthorne's fiction that Crews put forward in his well-known book entitled The Sins of the Fathers and that would assign to this physical manifestation a more conscience-related hidden meaning). More than hinting at some dubious and uncanny happenings to come, the laughter hints at an incongruous network of relationships established between author, characters and readers in their dealings with Old Nick. Indeed, on the one hand, Young Goodman Brown meets with a stranger whose description makes his dabbling with the dark world very clear, and yet he fails to realize it. This dramatic irony, even rather tragic irony, is the cause of all Young Goodman Brown's mishaps. When the devil7 laughs, it thus intimates this imminent threat to Brown's soul, and at the same time, and perhaps more importantly, alludes to and echoes, not to say ridicules, Brown's naive judgement, or the lack of it. It all comes to designing laughter as a subtle hoax. Hawthorne may have intended us readers to laugh at Brown, but also to connive if not with the devil per se at least at Brown's expense. The same can be said of the above quoted passage where Robin meets with the old passenger whose sepulchral laugh should have been a more than sufficient signal of alert.

Ultimately, Hawthorne appeals to the readers' connivance: we side with him in this humiliating (for Brown) situation. It partially legitimizes the devil's deportment as, like him, we are tempted to feel ourselves superior to him. His ignorance is not ours, and we are thus reassured. Yet, can we not detect in this laughter another tone of mockery, a veiled layer of import which only the truly conniving reader can reach out, and which is nevertheless aimed against himself as well? For, if we can laugh at Brown for his seemingly innocent and thoughtless behaviour, it is because we see him being made a fool of by the devil. It would only take a snapping of Hawthorne's fingers to reverse the situation. This time, Brown may well be the one to laugh. In this respect, Goodman Brown may well be Robin's real kinsman as they share the same characteristic naïve innocence, an innocence which would better deserve the name of lack of shrewdness, the very quality Robin thinks he is blessed with. We'll come back to this other typically (verbal) ironic device. For now, our point is about the ironic reversal of situations by which the characters are not aware of their being ridiculed by the overall happenings.

Let's return to this episode towards the end of 'My Kinsman' where Robin is going to attend 'some prodigious merrymaking', the object of which he thinks is some exterior and unknown one. The biting irony Hawthorne contrives here is precisely the reversal which turns the attendant of the show the subject of it, or rather the butt of it. Indeed, Robin does not realize (cannot in fact, maybe because of an overwhelming 'shrewdness'!) that the very own object of his quest, which he took so seriously and endeavoured to hard to carry out in a shrewd and stern manner, is going to be the very object of this carnavalesque procession. He is near to be crowned the fool of fools.

As it stands, Young Goodman Brown and Robin play the bad role, that of the scapegoat, by whom understanding and realization may become achievable and invade our minds and hearts.

Hawthorne thus abides by the seventeenth-century English critic Dennis's remark that "the design of Comedy is to amend the follies of Mankind by exposing them 8 " and succeeds in indulging in a satisfying humorous feast. Rather than urging the outside reader to be sympathetic with those victims, instead, Hawthorne makes the latter look so pathetic that it cancels altogether whatever pathos may be felt in such awful entrapping. Too much pathos kills pathos... Aristotelian pathos becomes marred, only the mocking shadow of itself.

The classification established by R. Dusenbery in his essay already cited has its worth, but only a limited one. Let's summarize in a few words the four categories of characters he discriminates according to the kind of laughter they utter. Basically, children' symbolize their innocence and spontaneity; the laughter of unmannered people (tavern and city people) betrays their corruption; materialistic men of the world have a long and loud laugh; the characters guilty of intellectual pride mock the world and themselves through their laughter; the last class includes satanic persons whose laughter provokes chaos on the earth 9 . Though we adhere to the symbolic importance of such interpretations 10 , we would like to qualify his findings. Indeed, where should we put Hawthorne's laughter? And the reader's ? Some reviewers will rightly argue that they fall out of these categories because they don't belong to the diegetic fictional world. Yet, we may as rightly create two extra categories: one which would include those who laugh at sorrow (and more particularly at others') and would legitimately be assigned to the gentle yet unsympathetic reader; the other class would be a oneman class, Hawthorne's privileged preserve. His arises above all other laughters. His is at one and the same time the first and ultimate to resonate.

As [Robin] turned to leave the room, he encountered a sneering glance from the boldfeatured personage whom he had before noticed; and no sooner was he beyond the door, than he heard a general laugh, in which the innkeeper's voice might be distinguished, like the dropping of small stones into a kettle. ('My Kinsman,' p. 7; our italics)

Can we not identify this innkeeper with our own author? Hawthorne is the ultimate keeper of the mansion that is his fictional world, and he cannot help but laugh at the silly creatures that populate it.

The stones that drop into the kettle epitomize, more concretely than symbolically, his harsh tone of disapproval.

What seems to be Hawthorne's sarcastic temper may well constitute his best weapon to cope with a stern, austere, mirthless Puritan philosophy of life which he strove to curb as best he could. Far from denying the existence of evil in the world, he preferred to laugh the matter off. Robert Allen Durr 9 R. Dusenbery, p. 288 10 Notwithstanding the seeming contradiction between children' innocent and gay laughter on the one hand, and Dusenbery's construing laughter as "gradation of evil" on the other, unless he sees innocence as the zero degree of the scale.

in his essay entitled "Hawthorne's Ironic Mode,» published in the 1957 December issue of The New England Quarterly, wrote that This unfailing recognition is at the root of his unfailing humor and irony. The "Good Creature", the vicious predilection in this New England world envious of his strict morality, is yet another caustic judgement against Hawthorne's hypocritical attitude: they condemned drinking as a hundred-year-old traditional vice, and yet indulged in its consumption. One of the root of evil is here made the object of a grotesque in an attempt to laugh at the contradictions of this Puritan tradition.

II.

Behind a laughter there is a cry. This almost proverbial statement superficially evidences what Louis D. Rubin, Jr. reminds us of in his introductory essay of The Comic Imagination, "The Great American Joke":

The highest accolade we give to a humorist is when we say that even so he is a 'serious' writer -which is to say that although he makes us laugh, his ultimate objective is to say something more about the human condition than merely that it is amusing. (p. 4)

This both alludes to the moral duty of the seriously humorous writer, the didactic function behind such an incongruous move, and to the fact that seriousness is at the bottom of everything. Along with this axiomatic principle, there is another one which is almost systematically applied to humorous writings: that of incongruity. Grossly stated, this means that a writers resorts to humorous pith when he feels a discomfiting gap between what is and what should be. Thus, humor would be a means to achieve a counterpoised depiction of two worlds completely afar from one another but which should in fact fuse together: the ideal and the real. Humor, in this perspective, appears to be endowed with a Janus-like quality, looking at reality yet, at the same time, looking jealously towards ideality. The critical quality of the former conceals and reveals the critical yet saddened sensitivity of the latter.

Incongruity can be, in the hands of ill-intentioned writers, or merely dexterous ones, better used as a way to mislead the readers. Resorting to humor can thus be conceived as a deceptive strategy.

Seen in this unflattering light, it is akin to lie and it furthers the already blurry relationship it has with truth and reality. Why a lie? We can envisage another interpretation, more positive. Indeed, it is no longer a deception if we accept the fact that what the humorous writer depicts as a real world is in effect a mocked real world, where "mocked" means "ridiculed", but also points to its plasterboard, stage-like quality. The characters wandering in their sorrowful universe are deluded, willy-nilly deceive others in their blinded state.

'No, no, neighbor!' cried Robin, flourishing his cudgel, and then thrusting its larger end close to the man's muffled face. 'No, no, I'm not the fool you take me for, nor do you pass, till I have an answer to my question. Whereabouts is the dwelling of my kinsman, Major Molineux?' ("My Kinsman," p. 10 ; our italics.)

Again, Hawthorne cannot help but grinning at the foolishness of his character. We could almost see him sighing with exasperation as he writes his story! Indeed, Robin is so absolutely persuaded that he is in the right and justified in his search, won't be made a fool of by other ignorant and inferior people. He believes in his high status and is convinced that he deserves respect and obedience (see the assertive cry 'No, no!' twice repeated) from others. In his very wish to be taken seriously in his inquiry for his relative, the townspeople cannot refrain from being submerged by a feeling of despise at the futility of such a quest. The bitter irony and truth are hard to swallow, so to speak, and Robin, despite all he can say or do (or threat to do) to defend himself and his earnestness, is exactly the thing he does not wish to be taken for: a fool. He is so blinded to his own self-sufficiency and self-conscious pride that his behavior becomes totally disproportionate to the situation (threatening an old man is not quite a proof of courage or shrewdness). The crucial point made by Hawthorne here is that the reader should not follow in Robin's footsteps and try to keep his mind clear, distinguish reality from fiction, and not be ridiculed in turn. They need reconsider and relativize their position in the universe. In this delusive game, the readers fall short of becoming the real manipulated victim if it wasn't for all the comic stones thrown by Hawthorne on our path to truth.

Speaking of wilful deception may be a way to akin Hawthorne to God. Characters (and readers) are played upon by the whims of an author who vicariously enjoys their mishaps. He plays the ultimate playwright, who directs his pawns in a stagey world of which he alone possesses the key to mystery. He sends signs for us to interpret. In the last sentence of "My Kinsman," we can spot one of these clues to the unfolding of the mystery, here the mystery being the grasping of Hawthorne's humor. ' […]. Or, if you prefer to remain with us, perhaps, as you are a shrewd youth, you may rise in the world, without the help of your kinsman, Major Molineux.' ("My Kinsman," p. 17; our italics). It being uttered by the gentleman, the sentence, and the phrase "a shrewd youth" in particular, become endowed with a forceful quality, and a totally meaning import. Yet, the attentive reader will not fail to notice that the recurring phrase about Robin's pretended shrewdness is here the only occurrence which is not uttered by Robin himself to himself but by someone exterior to him. Does this final reversal induce a reversal of meaning, and ultimately of our reading, turning a negative interpretation -Robin is in fact devoid of this quality -into a positive one -which privileges a more literal reading and holds Robin's shrewdness as the (fictional) truth? We do not think so. On the contrary, we clearly assume that it furthers and definitively prorogates the negative reading. He is not shrewd; he has become so thanks to all the trials he has gone through.

This realization of adulterated truth, or more accurately truthful lies -the world you are observing is your world but should not be like this and yet -is achieved through shrewd caution at not taking things at face value. Just like Robin doubts the truthfulness of the pretty mistress's words, the reader should also doubt the veracity and sincerity of Hawthorne's words: "Now her voice was the sweetest Robin had heard that night, the airy counterpart of a stream of melted silver; yet he could not help doubting whether that sweet voice spoke gospel truth." ('My Kinsman,' p. 9; our italics.)

Sometimes, this coming to terms with the real intention of the author takes place at the end, when the harm is done, or the joke played. As Robert Allen Durr rightly notes in his already cited essay: "There are passages […] where it is not until the very last sentence that we bring ourselves up short to realize the satiric intent which has operated tenuously throughout." (p. 487)

When the unveiling of the seriously farcical joke that Hawthorne has been playing down on us happens at the very last minute, it can either be as sarcastically orchestrated as the whole preceding development or, conversely, be as quiet and controlled in tone as it has been restlessly ironic. Again, here, the episode of the "prodigious merrymaking" in 'My Kinsman' helps us illustrate our thought.

Indeed, the fact that Robin feels the necessity to laugh may well influence our reading of the forthcoming event as it throws an illuminating light on the past ones. Moreover, Hawthorne masterly ridicules his plasterboard hero. If the latter has not had the heart (nor the chance) to laugh yet since the beginning of his journey, the reader certainly had more than one opportunity to enjoy this "prodigious merrymaking" that is Robin's quest for his relative. The author himself is, as we said, enjoying his character's predicament and would like his audience to react as lightly (and critically) as himself. In other words, in this scence, Robin is put in the readers' shoes to realize the whole absurd import of his quest. He has to take passively part of an outer fun show to achieve this brutal realization, so brutal that he cannot help bursting into a madly loud peal of laughter.

Speaking of intention allows us to move on to a related question, that of the purpose of humor.

What end does indulging in a comic mood serve? Reading Hawthorne's short fiction, one feels that a unilateral answer is hardly conceivable as he is decidedly bent upon multiple approaches. We must not deduce from our analysis that Hawthorne was completely devoid of sensitivity, that he was as stone-hearted as Ethan Brand. On the contrary, it would not be absurd to say that his sensitivity triggered his humor. Because he felt deep, deep down the injustice, the inhumanity and the ever-again necessity of the atrocities his Puritan ancestors made themselves guilty and shameful of, he could summon his natural humor to deal with his feelings. Or was it to quiet them down? Did he want to make fun of himself and his over-sensitive attitude towards his burdening past, as if to condemn himself to an everlasting destiny of sorrow and guilt? Or, on the contrary, did he want to mock his ancestors' and contemporaries' lack of sympathy by trifling with his characters and destinies? Whatever the reading, one cannot deny the underlying sympathy -whether original (in Hawthorne's heart) or aimed at (in the readers') in his humor: "While the function of laughter is in 'exposing all actual defect', the satiric exposure broadens human sympathies11 ".

Hawthorne knows how to make use of the tear-tinkling device that is exclamative intonation.

Indeed, in 'Wakefield,' the narrator often indulges in some exasperated yet saddened remarks, like the following one, which is near the beginning of the tale, when Wakefield is lost amids the crowd and is afraid of being spotted by his wife or some stranger: "Poor Wakefield! Little knoest thou thine own insignificance in this great world! No mortal eye but mine has traced thee." ('Wakefield,' p. 77). Those exclamations are imbued with a double feeling: commiseration and despise. Maybe it is despise in commiseration, or the other way around. We feel that we must feel sorry for Wakefield but at the same time we cannot help but grinning at his "insignificance" which he fails to realize. With Hawthorne, we cannot be all merry or all gloomy; there has to be a juncture crossroads where both feelings can meet and then go on their own way.

III.

This last part is going to be a proposed stream of thoughts. Studying the different episodes in Hawthorne's tales where we sense some humor at work, we cannot but help thinking of the relation this humor has with its linguistic manifestation. How is language used by Hawthorne to convey those different humorous effects? Does this not reflect Hawthorne's literary stance, which at once is an ideological and aesthetic position? More than an ideological stance or theoretically classical conviction indeed, humor in Hawthorne's works in general and his tales in particular seems to be an aesthetic stance, a stylistic tour-de-main which allows his performer to play with words, with language, and ultimately to enjoy his literary art for its own sake. Hawthorne seems to, if not outrightly advocate (due to his deep-rooted Puritan conscience), at least propose an aesthetic approach to humor writing and a belief in humor for humor's sake. One has to read between the lines to realize the far-reaching implications of such a stand. Indeed, if one satisfies oneself to a superficial and perfunctory reading, one has a remote chance of grabbing Hawthorne's aesthetic and pithy humor. One Ariane's thread is materialized in the semantic network that the author elaborates throughout his tale. In 'My Kinsman,'

for example, the constant repetition of the adjective "shrewd," and other lexies related to it ('cunningly', 'shrewdness') creates an ironic isotopy which partakes in this verbal humor.

As Hawthorne takes the risk to explore the obscure and pernicious depths of the human mind, heart and soul, he does so by using a somewhat inappropriate language, or turn of language. We do not intend to claim that Hawthorne is nowhere serious or constantly adopts a tongue-in-the-cheek tone visà-vis the tragic issues he tackles. We are just putting forward an aspect of his style and aesthetics which may be overlooked because apparently in complete contradiction with the latter feature of his works.

One element worthy of attention and study is Hawthorne's tendency to (voluntarily) merge together various modes of humorous writing categories. At times, one is quite at a loss as to what position adopt before a specific situation. Indeed, irony, sarcasm and satire fuse together to confuse the readers, unable to judge, dazzled as they are by the hybridity of Hawthorne's style. The meaning of the peculiar laugh of the passenger Robin meets is one species of this hazy style: "'I have -hem, hemauthority'" ('My Kinsman,' p. 5). The bracketing seems to be pointing to another level of meaning, maybe a level without meaning, at least in the diegetic world. Should we not hear in this 'hem, hem' the chuckling author, perhaps crying with laughing over his sheet of paper? In this perspective, the only raison d'être of this laughter would be to emphasize the self-conscious fictionality of the whole thing.

The author trifles with his material that is language: he shapes, molds and gives life to his words and thoughts in such a way that witticism can lurk behind humorous remarks. Hawthorne winks at his audience, offering them a profane performance. This indeed, in the eyes of some Puritan principled men, may be a bad taste joke, but for Hawthorne, at least partially, it may be his way of glancing back at History and into his story.

One of the functions of humor we alluded to earlier is a didactic one, or at least seemingly didactic. Indeed we argued that humor was a powerful weapon in the war against vices. Seventeenthcentury English writers thought so and ardently believed in the deep power that surface humor and irony could unleash. Indeed, humor, irony and satire achieve the same goal, though using different means (as far as linguistic and rhetorical means are concerned). These deliberately ambiguous postures are not without danger, a danger precisely provoked by (and, paradoxically, averted) the technical devices resorted to. Rhetorical questions, puns, caricatures (through hyperboles), irony -dramatic, tragic, comic, situational, verbal, metafictional -present the potential liability to be misinterpreted by foolish choice, who was in charge of the other part? All these questions haunt the text just as Wakefield haunts the vicinity of his own house for twenty years. The uneasiness and incongruous awkwardness of the situation are even more dramatized by the uncanny smile that Wakefield bestowed on his wife on his departure. We are told that after that fateful day, the smile will "flicke[r] across all her [Mrs Wakefield] reminiscences of Wakefield's visage." (p. 77) This silent and inner laughter is fraught with contradictory (to us) feelings: hap and distress, selfishness and sympathy (for his wife), pride and shameful foolishness. This same foolishness seems to be the prevailing feature and the "almost" rhetorics of the tale helps alluding in an ironical way to the other, wiser alternative that Wakefield could have opted for: "Almost repenting of his frolic, or whatever it may be termed, Wakefield lies down betimes, and starting from his first nap, spreads forth his arms into the wide and solitary waste of the unaccustomed bed." ('Wakefield,' p. 78; our italics)

His Puritan background somewhat went in the way, put a restraint on both his thoughts and writing. Humor was a way out for him, a veiled safety exit through which he could evacuate all the pent-up frustrations and thus keeping a mental balance which could, in return, feed his imagination.

With Hawthorne there seems to be an interdependent mechanism at the origin of his writing. He uses his Puritan religious and ethical legacy to motivate his imagination which invokes and stimulates his humor, thereby enabling him to remain faithful to his deep-hearted principles, which are partially in contradiction with that legacy. Thus, to him, the latent eventuality of being misinterpreted might not have affected him: the surface story would still be in harmony and in keeping with the Puritan thoughts and morals that it is supposed to follow. It would take only distorted or unsafe minds to read anything else but the letter of the story. In Hawthorne's case, subversion is more pungent when undertaken in a surreptitious manner.

Louis B. Wright, in his essay entitled "Human Comedy in Early America,» states that "writers of diaries and journals often provide insights into the life of the times that are entertaining and humorous, even though the authors themselves did not intend to be comic 13 ." This can be partially accounted for by the changing values -whether they be moral, religious or social -that were obtaining at the time of the writing. We, readers of the 21 st century, do not read, perceive, understand or even accept the same sets of values as nineteenth-century readers. In Hawthorne's case, though, it seems rather the other way around. Sometimes, he may have intended (we prefer to remain cautious) to be comic but was nevertheless taken seriously, at least in his own time and place. Accepting this potentially subversive aspect of Hawthorne's writing is one step toward a rediscovery of his heart and mind where, despite the considerably dark space allotted to gloom and sorrow, there was some room left for lightness and, if not happiness, at least comedy. Man, Hawthorne understood that, is a two-fold creature, made up of two contending yet coexisting entities, gloomy sorrow and wan joy. Hawthorne paralleled the earthy and hybrid grossness (to use Hennig Cohen's phrase14 ) of human nature with the earthy and heterogeneous grossness of the nature of comic language. Hawthorne thus alternates between light humor and grave seriousness, as he goes back and forth from a grave humor to a light seriousness. His characteristic tendency to set his decors on the border that separates the fictional and the historically real world, has a stylistic pendant in this register-based swinging. In the words of Melville in Moby Dick, "There is a wisdom that is woe; but there is woe that is madness.15 ". Amidst the darkness of the world and the inner blackness of the human heart, man must not, at least should not, lose his soul. To counteract the horrifying maze of the latter, Hawthorne used language as a means of humorous amazement. Man should, if he wants to keep his mind whole and sane, divert from the orthodox austere road to take a more heterodox because less severe path.

One further element which may comfort us in our interpretation of Hawthorne's tales as being (masked) versions of comic performances, is the fact that some of his tales can actually be regarded as, this time, openly humoristic stories.

The fact, thus absolutely stated, is not very uncommon, norwithout a proper distinction of circumstances -to be condemned either as naughty or nonsensical. Howbeit, this, though far from the most aggravated, is perhaps the strangest instance, on record, of marital delinquency; and, moreover, as remarkable a freak as may be found in the whole list of human oddities. ('Wakefield,' p. 75;our italics) This preliminary comment is interesting in more ways than one. The prevailing negative tone (see our italicized phrases) presents the judgements that we may be inclined to utter yet should not, if we are to believe the narrator's word for it. In effect, the negative is double: the narrator, on the one hand, admits in a round manner the casual quality, the relative commonness of the related fact ("not very uncommon" means in fact "rather common") and, on the other hand, prevents our liably (and legitimately?) radically unfavorable opinions towards this "not very uncommon" story. Why should the narrator feel obliged to introduce the "story, told as truth" in such a preventive and defensive way if not to achieve the reverse aim? Indeed, only by hinting at and, at the same time, dismissing right from the beginning, the possibility of construing the story to unfold as "naughty or nonsensical" does he pave the way for such an interpretation and, in fact, validate the latter as the one and only interpretation to be found in the moral of the tale. Thus, the negative and modalizing linguistic devices are the very tool by which Hawthorne contrives this reversal of interpretation, and, thereby, his humorous fit.

We thus agree with Hennig Cohen when he slyly propounds that "we have here [with the tale entitled "Mrs Bullfrog"] a comic version of "The Birthmark." He further affirms that "Although comic, Hawthorne is sermonizing as usual" and attracts our attention to the fact (which may contradict our

[

  Hawthorne] was at odds with [the intellectual temper of his age] because the transcendental philosopher, like the reformer, disregarded one factor which to Hawthorne was basic: the real and unavoidable existence of evil and, concomitantly, the original corruption of the human heart.(p. 492)

  His humor can be labeled a didactic one, designed to, if not mend and right wrongs, point out human defects,

thereby perpetuating the tradition of seventeenth-century writers like Swift. Hawthorne thus differs from his Concord friend Ralph Waldo Emerson as the latter did not really hold laughter close to his heart. Without completely distrusting this typically human trait in the attempt to improve mankind, the Transcendental philosopher believed and hoped that such a device would eventually no longer be needed to reach nobler heights: this is what John Bryant intimates in his Melville And Repose: The words are by the Boston critic E.P. Whipple whom he also quotes] Transcendence obviates it. 'Man thinking' does not need to laugh.

" (p. 43)

R. Dusenbery, "Hawthorne's Merry Company: The Anatomy of Laughter in the Tales and Short Stories," in PMLA, Vo l. 82, No.

(May 1967), pp. 285-288 2 We consider them as kinds of humor, and even manifestations of it. So whenever we shall refer to humor, we implicitly allude to the hyponyms, though we are perfectly aware of finer subtleties.

In this respect, his juvenile journal The Spectator is a pungent piece of evidence of his characteristic sense of humor sometimes targeted at and triggered by such dreadful events as deaths. His dark humor seems so natural to him that it would be over-interpret, if not totally misinterpret it to construe it as an Aristotelian legacy.

Here, we take for granted the symbolic interpretation according to which this stranger impersonates the Devil. When we refer to the devil, we thus allude both to this character and the one he is supposed to represent.

Cited in The Comic Imagination, "Introduction: The Great American Joke", op.cit., p. 4

Melville and Repose, op.cit., p. 42

In The Comic Imagination, p. 23.

In The Comic Imagination, p. 90.

Cited by Hennig Cohen's essay in The Comic Imagination, p. 95.

In The Comic Imagination, p. 99-100.

Arlin Turner, "Comedy and Reality in Local Color Fiction,

1865-1900" in The Comic Imagination, p. 173.. Turner, though, applies this to Mark Twain, and not Hawthorne.

the audience to which they are addressed. Misunderstandings are around the corner and can annihilate the possibility of reaching the author's actual and original aim.

If the reader choose, let him do his own meditation; or if he prefer to ramble with me through the twenty years of Wakefield's vagary, I bid him welcome; trusting that there will be a pervading spirit and a moral, even should we fail to find them, done up neatly, and condensed into the final sentence. Thought has always its efficacy, and every striking incident its moral. ('Wakefield,' p. 76) Here, the moral intent of the tale is clearly stated. Hawthorne does not shy away from an outright didacticism. This characteristically moralizing idiosyncrasy should not, however, mislead us and induce us to overlook the sarcastic and ironical tones that lie underneath the surface and that the author adopts more often than not. Both modes -ironic and humorous 12 -seem, under Hawthorne's pen, to intermingle, to interrelate: because he is ironical, he can venture to preach a moral lesson, and as he sermonizes, he twists his moral, or at the very least, the telling of the moral. Does it adulterate the latter or, on the contrary, give more strength and relevance to it? Here again, a bit of both. This perniciously ambiguous and ambivalent effect has been noted: it is inextricably linked to the exercise, the nature of which requires the author to be aware of and go along with the rules of the game.

Hawthorne was no exception. He even seemed to be enjoying it. One other relevant stylistic item is the rather typical tendency to modalize his discourse. Indeed, the adverb "almost" is one which recurs in Hawthorne's short (and even long) fiction. It partakes of his whole rhetorics of appearance and reality.

It also blurs the borderline between the narrator's involvement in the telling of the story, thereby marring, or at least questioning his reliability, and the character's diegetic focalization in the unfolding of the story. This blurring can be construed as yet another way of conveying ironical or humorous signals to the readers at the character's own expense.

He holds out his hand; she gives her own, and meets his parting kiss, in the matter-ofcourse way of a ten years' matrimony; and forth goes the middle-aged Mr. Wakefield, almost resolved to perplex his good lady by a whole week's absence. ('Wakefield,' p. 77; our italics.) What is "almost resolved" supposed to mean? Was Wakefield totally at the origin of this mock-epic adventure (see the use of the word "equipment and the overall mock-melodramatic emotions underlying the farewell scene)? Was there a chance of him giving up the whole journey altogether? Was he forced to carry it out? Who made him? If Wakefield has a part of responsibility in this fatefully 12 Here again we use the term "humorous" as a hyperonym.

own interpretation) that "the story made [Hawthorne] uneasy and he confided in his notebook, "as to Mrs Bullfrog, I give up her to the severest reprehension.'" 16 We do not, however, support this latter position (the sermonizing tone). For, this after-the-event sentiment does not erase the reality and sincerity felt at the time of the writing. Thus, the remorse Hawthorne feels is a poor eraser of the writing and artistic act, and may well be another cynically humorous gibe at his own cynical humor. This inclination to rewrite himself seems to constitute the characteristic key to fathoming the deepest and innermost recesses of Hawthorne's mind. He "manipulates language as itself the material of comedy 17 " Before we conclude, we would like to take two examples of the meta-linguistic use of humor. The first one is found after the passage where the narrator recounts the chanced meeting between Wakefield and his wife after twenty years: "Perhaps he was so. [The narrator, here, takes on Wakefield's own selfpitying exclamation: 'Wakefield! Wakefield! You are mad!']" ('Wakefield,' p. 80;, our italics) The second example is found just before the narrator's concluding moral: "As [Wakefield] passes in [here, he finally decides to cross the threshold of his housedoor], we have a parting glimpse of his visage, and recognise the crafty smile, which was the precursor of the little joke." (p. 81; our italics) Here again, the epistemic modality reinforces the narratological, diegetic as well as moral distance which parallels in the linguistic and metafictional world the spatial distance that Wakefield maintained during twenty years in the fictional world. The lexical item "joke" explicitly and outrightly condemns Wakefield's doings -his part of responsibility in not wanting to go back out of sheer self-centered pride -and condones this turn of event. Pride is despicable, all the more so when the its detrimental consequences affect other people. This moral message is conveyed through a metalinguistic device, as the word refers to the very thing that Hawthorne has been doing all along: taking his readers for a joking ride, as Wakefield took his wife for a ride.

Bitter truths need be sweetened down for mankind to be able if not to accept them at least to do with them and go along their lives as if there was nothing the matter. Serious humor, then, seems perfectly applicable to Hawthorne, especially regarding his predilection for contradictions and dualisms.

Chiaroscuro effects and polarities become in this perspective manifestations of as well as translations from the real-to-ideal wished-for passage, thus denoting and connoting a certain resignation from the author's part. Indeed, this laughing mood protects him from the harsh reality: it is the mask and veil behind which Hawthorne can observe passively the world, criticize it yet cannot alter it beyond his written caricature of it.

Is what George Core says of Henry James' The Ambassadors applicable to Hawthorne, namely that "The irony [of his tales] is dissolved by its comedy, even as the moral dimension is subordinated to the comic vision 18 ". The interrelatedness and interconnectedness between irony, comedy and morality all betoken of the close relationship they have with language. Hawthorne's humor would in this respect be better qualified as a meta-humor since layers of interpretation are superimposed to form a miscellaneous fabric. He uses language to word his humor which, in turn, serves to hint at this linguistic device and designs. The interplay of langauge and humor may well be Hawthorne's own Puritan background.

Selected bibliography

The following references include the books that nourished our reflections on the subject. The ones preceded by an * are the ones that are actually cited in the essay.


Cristian Dumitrescu An
email: cristiand43@gmail.com

Cristian Dumitrescu

An extension of Schöning's algorithm

Keywords: NP-complete problems, 3SAT 1 M, 2 M, 3 M, … …

Introduction

The importance of efficiently solving NPcomplete problems is due to the fact that this would imply that all the other problems belonging to the NP class can be efficiently solved in a constructive manner (the algorithms can be generated for all of them through polynomial -time reductions).

It is well known that 3SAT is NP-complete.

Proposition 1. (see [Papadimitriou,94] and [START_REF] Hopcroft | [END_REF]). 3SAT is NPcomplete.

Proof. For the proof, see (see [Papadimitriou,94] and [START_REF] Hopcroft | [END_REF]).

We will first present a well known randomized algorithm for 3SAT. This is Schöning's algorithm from 1991 (see [Schöning, 1991]). We also note that Papadimitriou also discussed a similar algorithm for 2SAT in 1991 (see [Papadimitriou, 1991]).

It is known that Papadimitriou's algorithm finds a solution in quadratic time with high probability for 2SAT. Only exponential bounds are known for Schöning's algorithm for 3SAT.

Stochastic local search algorithms played an important role, related to SAT solvers. This includes the random walk algorithm of Papadimitriou for 2SAT, and Schöning's extension of this algorithm for 3SAT.

Schöning's algorithm for 3SAT

Input: a 3SAT expression in 𝑛 variables.

Guess an initial truth assignment, uniformly at random.

Repeat 3 • 𝑛 times:

If the expression is satisfied by the actual assignment, stop and accept.

Let C be some clause not being satisfied by the actual assignment. Pick one of the three literals in the clause at random, and flip its truth value.

Update.

Stop and reject, the expression is not satisfiable.

Note that these algorithms involve random walks on the boundary of the truth assignment hypercube (the unit hypercube where each vertex represents a truth assignment). The fundamental and new idea in this article is to consider stochastic local search algorithms through the bulk (the interior) of the truth assignment hypercube (which becomes the truth valuation hypercube). This will become clear in section 2, when the concept of truth valuation will be introduced. We will formulkate a conjecture and present strong arguments that the algorithm presented in section 2 is polynomial (even for the worst case instances of 3SAT).

A different type of algorithm (this is a hill climbing algorithm, not directly related to Papadimitriou or Schöning's algorithms), but also based on the concept of truth valuations, is given in [A2].

Still another type of algorithm (the clustered Sparrow algorithm) is presented in [A4].

The extension of Schöning's algorithm

We assume that the reader is familiar with the random walk model (based on the Hamming distance to a solution) associated with the algorithm. This is discussed in detail in [Schöning, 1991], and [Papadimitriou, 1991].

Definition 1. In the following, M will be a natural number, in general smaller than n. A truth valuation v(x) is a function from the set of variables {x 1 ,x 2 , x 3 , … … . x n } to the set of values {0,

rational number from the set {0, 1 M , 2 M , 3 M , … … . , M-1 M , 1}
. We note the difference between a truth valuation and a truth assignment, where the truth assignment for a variable can be only 0 or 1. We also note that in general (as used for the truth valuation of a clause), a truth valuation is a real value in the interval [0, 1]. Definition 2. Given two truth valuations for n variables (𝑣 1 (x 1 ), 𝑣 1 (x 2 ), 𝑣 1 (x 3 ), … … 𝑣 1 (x 𝑛 ) ) , and (𝑣 2 (x 1 ), 𝑣 2 (x 2 ), 𝑣 2 (x 3 ), … … 𝑣 𝑛 (x 𝑛 ) ) , the Hamming distance between these truth valuations is by definition

𝑑(𝑣 1 , 𝑣 2 ) = |𝑣 1 (x 1 ) -𝑣 2 (x 1 )| + |𝑣 1 (x 2 ) -𝑣 2 (x 2 )| + ⋯ … . . + |𝑣 1 (x 𝑛 ) -𝑣 2 (𝑥 𝑛 )|.
The normalized Hamming distance is just the Hamming distance divided by the length of one step, which is

1 M . Definition 3. The truth valuation of 𝑥 ˅ 𝑦 is v(x ˅ y) = v(x) + v(y) -v(x) • v(y).
The valuation of the negation of a variable ¬x is v(¬x) = 1 -v(x). It is clear that if we are given a truth valuation for the n variables that appear in a 3SAT expression, then for any 3SAT clause we can calculate the truth valuation of that clause

v(x ˅ y ˅ z) = v(x) + v(y) + v(z) -v(x) • v(y) -v(x) • v(z) -v(y) • v(z) + v(x) • v(y) • v(z)
. The truth valuation of the whole 3SAT expression is the product of the truth valuations of all the clauses.

Extension of Schöning's algorithm for 3SAT

Input: a 3SAT expression in 𝑛 variables. Initialize all variables with the truth valuation 1 2 (or following a uniform distribution on the states of the class 𝑆 0 , described below).

Repeat 4 • 𝑛 2 • 𝑀 2 times:

If the current truth valuation is a satisfying truth assignment, then stop and return the satisfying truth assignment.

Let C be some clause that has a minimal truth valuation. If there are more than one, then pick one at random. . Choose one of the literals in the clause at random ,and if its current truth valuation is not 0 or 1, then with equal probability

Stop and reject, the expression is not satisfiable.

The purpose of this paper is to prove that this algorithm finds a solution (if it exists) with high probability. We will need some preparatory propositions.

Proposition 2. We consider the case of one dimensional symmetric random walks with one unit steps (like the coin tossing game). For fixed t, the probability that the first passage through r occurs before epoch t

• r 2 tends to √ 2 π • ∫ e -1 2 •s 2 ds ∞ 1 √t = 2 (1 -R( 1 √t
)) , as r → ∞ , where R is the normal distribution.

Proof. For the proof, see [Feller, 1968], chapter 3. This means that the waiting time for the first passage through r increases with the square of r. The expected traveled distance in r 2 steps is r.

We note that similar to the random walk model ( [Schöning, 1991], and [Papadimitriou, 1991]), we have here a Markov chain. At any moment, if the current truth valuation of the variable is not 0 or 1, then the Hamming distance from the current truth valuation (for all the n variables) to the truth assignment solution (if it exists) can increase or decrease by . But at certain moments, the Hamming distance will increase or decrease with probability 1 (when the current truth valuation gives the corresponding variable the value 0 or 1). We do not have a pure random walk, as in the original models. We will call this the primary Markov chain, associated to the Hamming distance to a solution. The states of the primary Markov chain indicate the Hamming distance towards a solution.

We also note that we have n one dimensional symmetric random walks with reflecting barriers at 0 and 1 (each such random walk is associated to the truth valuation of a single variable). We will call these the secondary random walks with reflecting barriers. The states of the n secondary random walks with reflecting barriers indicate the current truth valuation of the corresponding variable.

Proposition 3. The secondary random walks with reflecting barriers have stationary distributions.

Proof. In the secondary random walks with reflecting barriers, when we say that we are in state The probability transition matrix is:

                                       0 1 0 0 0 0 0 0 2 1 0 2 1 0 0 0 0 0 0 2 1 0 2 1 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 2 1 0 2 1 0 0 0 0 0 0 2 1 0 2 1 0 0 0 0 0 0 1 0                  A If we write ( 𝜋(0), 𝜋 ( 1 𝑀 ) , 𝜋 ( 2 𝑀
) , … … . , 𝜋(1) ) for the stationary distribution, it will be the solution of the system of equations (this is a 1 × (M + 1) row matrix multiplied by a (M + 1) × (M + 1) square matrix):

( π(0) π ( 1 𝑀 ) π ( 2 𝑀 ) … … . π(1) ) • A = ( π(0) π ( 1 𝑀 ) π ( 2 𝑀 ) … … . π(1) ) .
When we solve this system of equations, we will find:

π(0) = π(1) = 1 2M π ( 1 𝑀 ) = π ( 2 𝑀 ) = π ( 3 𝑀 ) = ⋯ … . = π ( 𝑀-1 𝑀 ) = 1 M .
This stationary distribution is an equilibrium distribution. We need some results related to the convergence towards a stationary distribution for periodic chains.

Definitions 4. Two states in a Markov chain are in the same class if we can go from one to another in a finite number of steps with positive probability. A Markov chain is said to be irreducible if all states are in the same class. A recurrent state is one for which the probability that the Markov chain will return to it after a finite time is one. Assume that state j is a recurrent state. Let I = {n ≥ 1; p n (j, j) > 0} , and let d be the greatest common divisor of I. We call d the period of state j . A chain with period 1 is said to be aperiodic. All states in the same recurrent class have the same period.

Proposition 4. Suppose the Markov chain M is irreducible, recurrent and all states have period d. Fix x in S (the set of states), and for each y in S, we let K y = {n ≥ 1 ; p n (x, y) > 0}. Then the following statements are true:

(i) There is an

r y ∊ {0, 1, … … , d -1} so that if n ∊ K y , then n = r y mod d . (ii)
Set S r = {y ; r y = r} for 0 ≤ r < d . If y ∊ S i and z ∊ S j and p n (y, z) > 0 , then we have n = (j -i) mod d. (iii) S 0 , S 1 , … … … . , S d-1 are irreducible classes for M d (the dstep chain constructed from M), and all states have period 1 (this is called a cyclic decomposition of the state space).

Proof. For the proof, see [Durrett, 2010], chapter 6. Proof. For the proof, see [Durrett, 2010], chapter 6.

Examples. We will look at the secondary random walks with reflecting barriers for different values of M.

We note that the case M = 1 corresponds to the original version of Schöning's algorithm. In this case the transition probability matrix is A = ( 0 1 1 0 ) . We see that

A 2 = I (the identity matrix) . We have two states, state 0 (when the truth valuation of the variable is 0), and state 1 (when the truth valuation is 1). We have the transition probabilities p(0, 1) = p(1, 0) = 1 . The stable distribution of this chain is π(0

) = π(1) = 1 2
. The chain is periodic with period d = 2. The cyclic decomposition of the state space is S 0 = {0}, S 1 = { 1 } . In this case, we have p 2m (0, 0) = p 2m+1 (0, 1) = 1 . If we start in state 0, an example of a path taken by this chain is 1, 0, 1, 0, 1, 0, … … … …. We see that at any odd time, the chain is in state 1 , and at every even time the chain is in state 0. If we choose a state at random from a given path, we recover the stationary distribution π(0) = π(1) = 1 2 .

We will now consider the case 𝑀 = 2 in greater detail. In this case the transition

probability matrix is A = ( 0 1 0 1 2 0 1 2 0 1 0 ) . We see that A 2 = ( 1 2 0 1 2 0 1 0 1 2 0 1 2
) , and we also see that A 3 = A . We have three states, state 0 (when the truth valuation of the variable is 0), state ), and state 1 (when the truth valuation is 1). We have the transition probabilities p (0, Proof. The proof is immediate from proposition 4 and theorem 1. Definition 5. If the current truth valuation of a variable is 0, but the satisfying truth assignment for this variable is 1, or if the current truth valuation of a variable is 1, but the satisfying truth assignment for this variable is 0, then we say that this will be a positive reflection. In this case, in the primary Markov chain, the Hamming distance to a solution will decrease with probability 1.

If the current truth valuation of a variable is 0, and the satisfying truth assignment for this variable is also 0, or if the current truth valuation of a variable is 1, and the satisfying truth assignment for this variable is also 1, then we say that this will be a negative reflection. In this case, in the primary Markov chain, the Hamming distance to a solution will increase with probability 1.

The states i M , with 1 ≤ i ≤ M -1 will be called intermediate states.

In the algorithm, choosing a variable to change its truth valuation is equivalent to running one of the secondary random walks (the one associated to the variable chosen) for one step, and that is equivalent to one step performed by the primary chain.

Conjecture. At least for large values of M (comparable to n), the algorithm above will find a solution to a 3SAT problem (if it exists) in polynomial time, with high probability.

Arguments in favor of the conjecture. We have to study the ergodic properties of the primary Markov chain described above. For this purpose, we use proposition 5, relations (1) -( 6). We have to consider the two step Markov chain, on one of the cyclic classes S 0 , or S 1 . As an example, for the case 𝑀 = 2 , we have S 0 = {0, 1} , S 1 = { 1 2 } . For the two step chain, we have the probabilities :

p ( 1 2 → 0 → 1 2 ) = p ( 1 2 → 1 → 1 2 ) = 1 2
. We can couple our chain with a symmetric random walk. For each variable, starting in the state 1 2 , the chain visits the correct truth assignment, or the incorrect one with the same probability 1 2 . We know from proposition 2 that for a symmetric random walk, the expected traveled distance after N 2 steps is of order of magnitude N . In the context of our two step chain, this means that after N 2 steps, there might be a sufficiently large excess of variables that visit the correct truth assignment. Of course, this is just a heuristic argument, but the study of the ergodic properties of the primary Markov chain could lead to the conclusion that its behavior resembles the properties of a symmetric random walk, and in this case we know that a quadratic number of steps is sufficient , in order to find a solution with high probability.

Observation 1. There is an interesting geometrical interpretation. The n random walks with reflecting barriers (one associated to each variable) generate a random walk inside the truth valuation hypercube. The truth valuation hypercube has a side length of 1 (but we keep in mind that M is the minimum number of steps for a variable to change its truth assignment from 0 to 1 or from 1 to 0), and its main diagonal has the length √n . We could assume that the random walk starts at (0, 0, 0, … … . . , 0) , and it reaches the vertex of the hypercube that represents the truth assignment solution . As a result of the construction, this n -dimensional random walk never exits the interior of the hypercube, even if at times it can take place on its boundary. Also, this is not a perfectly symmetric random walk, because at each step, it follows the direction of the variables involved in minimal clauses (clauses with a minimal truth valuation). This will give our random walk a general "drift" direction towards the solution vertex of the truth valuation hypercube, and we also know that the distance that has to be travelled is less than √n. Since the distance travelled scales up as the square root of the number of steps performed by the algorithm, this means that a quadratic number of steps (up to a factor that depends on M ) are far more than sufficient, in order for the algorithm to hit a solution. I emphasize that this is only a heuristic proof, and more work needs to be done in this direction.

Observation 2. We also note that this is only one version of this type of algorithm. Other versions or improvements are possible. The original Schöning algorithm ( M = 1 ), relies only on reflections. In the version of the algorithm presented here, we try to minimize the effect of reflections, and rely instead on intermediate steps to drive the primary Markov chain towards a solution.

Discussion and conclusions

For general implications, related to efficiently solving NPcomplete problems, see [Fortnow, 2013]. An interesting application is related to the problem of automated theorem proving using an efficient algorithm for NPcomplete problems (see [A1]). The impact of this type of algorithm in mathematics is obvious. All unsolved problems at the present time (if they allow proofs that are not too long, within the axiomatic system that we work with, for example, with the information content equivalent to less than 10000 journal pages) will be quickly solved. If NP complete problems can be solved efficiently, better AI system can be designed. In industry, transportation problems, logistics, and manufacturing planning will be significantly improved. In medicine, these algorithms will lead to the design of better drugs and treatments (protein folding and its relation to NP complete problems). Also the crypto community must redesign their encoding and decoding procedures (and public key cryptography must be replaced). Basically, any field of activity that requires intellectual effort can benefit from these types of algoritms. The main purpose of this paper is to open new ways to approach this interesting problem.

Aknowledgements.

I emphasize that Professor Fortnow's book ( [Fortnow, 2013]) was a great source of inspiration and motivation that led me to seriously consider this problem. Also, I received some feedback related to previous versions of my work from Professor Uwe Schöning , Professor Lance Fortnow, and Professor C. Papadimitriou. I also discussed some of the arguments presented above with Eric Demer , graduate student at University of California, Santa Barbara, who also corrected a previous error that I had in my work. The clustered Sparrow algorithm from [ A4] was developed in collaboration with Dr. Anastasia-Maria Leventi-Peetz (BSI, Germany). I am grateful to all. In the same time, I take full responsibility for any omissions present in my work.

Appendices

A1. Godel's letter to John von Neumann. In his letter, Godel writes: "One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols). Let 𝜓(𝐹, 𝑛) be the number of steps the machine requires for this and let 𝜑(𝑛) = 𝑚𝑎𝑥 𝐹 𝜓(𝐹, 𝑛). The question is how fast 𝜑(𝑛) grows for any optimal machine" (see [Godel, 1956]. Now we consider this. In [START_REF] Hopcroft | [END_REF], we have theorem 13.1, at page 325 (a version of the Cook -Levin theorem), where it is proved that for each Turing machine (deterministic or nondeterministic) M that is time bounded by a polynomial 𝑝(𝑛), a log-space algorithm exists, that takes as input a string x and produces a Boolean expression 𝐸 𝑥 that is satisfiable if and only if M accepts x.

This means that the process of seeking a proof (of reasonable length) of a mathematical statement can be completely automatized. With the algorithm presented in this paper, Godel's vision can be made reality.

A2.

We are given a 3SAT expression E. A positive literal represents the variable itself, a negative literal represents the negation of a variable. For each occurrence of a variable x (in a positive or negative literal) within the expression we introduce a new variable x i , and form the modified expression E*. We also have to include a conjunction of clauses that state that the variables x i have the same truth assignment. The conjunction (x i ˅ ˥ x j ) ˄ (˥ x i ˅ x j ) has the truth value 1 if and only if the variables x i and x j have the same truth value. In general, the variables x 1 , x 2 , x 3 , … … . . , x m have the same truth value if and only if the conjunction (x 1 ˅ ˥ x 2 ) ˄ ( x 2 ˅ ˥ x 3 ) ˄ (x 3 ˅ ˥ x 4 ) ˄ … … … . ˄ (x m-1 ˅ ˥ x m ) ˄ (x m ˅ ˥ x 1 ) has the truth value 1. In the modified expression E*, each variable appears in at most three clauses, either in two positive literals and one negative, or in two negative literals and one positive.

In other words, each variable x appears only in a three variable clause ( x ˅ α ˅ β ) (or it could be ( ˥x ˅ α ˅ β ) ) , and in a couple of two variable clauses ( x ˅ ˥ γ) and ( ˥ x ˅ θ). Each variable appears only in the conjunction of these clauses ( x ˅ α ˅ β ) ˄ (x ˅ ˥ γ) ˄ (˥ x ˅ θ) . We now consider the valuation of these clauses , in terms of the valuations of each variable that appears in these clauses (we keep in mind that the truth valuation of a variable is a real number in the interval [0, 1], in this appendix). We calculate the valuation of each of the three clauses where the variable x appears.

v( x ˅ α ˅ β) = v (x) + v(α) + v(β) -v(x) • v(α) -v(x) • v(β) -v(α) • v(β) + v(x) • v(α) • v(β) . v(x ˅ ˥ γ) = v(x) + v(˥ γ) -v(x) • v(˥ γ) v(˥ x ˅ θ) = v(˥ x) + v(θ) -v(˥ x) • v(θ) We also keep in mind that v(˥ x) = 1 -v(x) and v(˥ γ) = 1 -v(γ). The function f(x) = v( x ˅ α ˅ β) • v(x ˅ ˥ γ) • v(˥ x ˅ θ
) becomes a cubic polynomial in the truth valuation of the variable x, if we look at the valuations of α, β, γ, and θ as fixed parameters. We can then calculate the valuation of the variable x, such that the expression f(x) takes a maximum value in the interval [0, 1], and change the valuation of x to that value. We remember that we want to maximize the truth valuations of all the clauses in the expression E*, until they all become 1. We can repeat this process for all the variables involved in the expression E*, over and over again, until all clauses (and thus the whole expression E*) has maximum truth valuation 1. The problem is that we can get stuck in a local maximum, even if the truth valuation of every clause is not the maximum 1. In that case, we can reinitialize the truth valuations of the variables at random and start all over again, until we enter the basin of attraction of the global maximum, that we are seeking. At each step, the truth valuation of the whole expression E* can only increase or stay the same.

A3.

If in a solution truth assignment, a variable is given the truth assignment 0, then the truth assignment 1 is a positive reflection point, and the truth assignment 0 is a negative reflection point, for the random walk with reflecting barriers associated to this variable. If in a solution truth assignment, a variable is given the truth assignment 1, then the truth assignment 0 is a positive reflection point, and the truth assignment 1 is a negative reflection point, for the random walk with reflecting barriers associated to this variable.

We consider the random walks with reflecting barriers associated to each variable. We consider the case M = 4. In this case, we have the states 0,

                                                  0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 0 2 1 2 0 2 1 0 2 1 0 2 1 2 0 2 1 0 2 1 2 0 2 1 2 0 2 1 2 0 1 1 1 1 1 1 1 1 1 1 1 1 1 2 k k k k k k k k k k k k k k k k k A                                                  1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 2 0 2 1 0 2 1 2 0 2 1 2 0 2 1 2 0 4 1 0 2 1 0 4 1 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 0 2 1 2 k k k k k k k k k k k k k k k k k A
These probability transitions govern all the odd and even steps of the random walk with reflecting barriers associated to the variables. We see that if a variable starts in a positive reflection point, then at even steps, it is slightly more likely that the associated random walk with reflecting barriers will hit the positive reflection point, rather than the negative reflection point. It is also more likely that at odd steps, the random walk will hit points closer to the positive reflection point, rather than closer to the negative reflection point. Without restricting generality, if we assume that most of the variables start in positive reflection points (for example, we can initialize all the variables with 0 or we can initialize all the variables with the truth value 1), it is then likely that overall, the positive reflection points will be hit more often than the negative reflection points, but this also depends on the structure of the 3SAT expression, and the complex dynamics of the primary Markov chain. It is worth noticing that if all the variables are initialized with the truth valuation 1 2 , then at even steps, it is as likely that the random walk with reflecting barriers (associated to any variable) will hit a positive reflection point, as it is likely that it will hit a negative reflection point (in both cases the probability is 1 4 ).

A4. The clustered Sparrow algorithm

We start from a 3SAT expression E, and we perform the conversion to the clustered SAT expression E*, where each variable appears in at most 3 clauses. For a clear presentation of the procedure, see proposition 9.3, page 183, in [Papadimitriou, 1994].

We note that the assignments marked with * satisfy the cluster (all clauses in the cluster are satisfied). The flips 0 → 1 and 1 → 0 refer to the primary variable x, when all the other literals do not change (under the current truth assignment). The last two columns represent the make minus break quantity Δ = make -break , where "make" represents the number of clauses that change from unsatisfied to satisfied, as a result of the flip, and "break" represents the number of clauses that change from satisfied to unsatisfied, as a result of the flip. The algorithm only touches unsatisfied clauses (or clusters), so the satisfying assignments do not have a Δ value in the corresponding column (a possible exception is between assignments 15* and 16*, since the cluster is left satisfied and Δ = 0 ).

We will call a positive flip, a flip that has the value of delta strictly positive Δ > 0. We will call a negative flip, a flip that has the value of delta strictly negative Δ < 0 . We will call a null flip, a flip that has the value of delta 0, Δ = 0 .

We note that all flips are either positive or null, with one exception, the second assignment in the table (the delta value marked in red). Also, we note that if at a given moment, a negative flip occurs, we see that the cluster is still unsatisfied, allowing for a positive flip later. Thus, at later stages, the flip will be reversed with high probability, if the change of the secondary variables in the cluster do not make the cluster satisfied before that.

Lemma. If the clustered expression E* contains clusters with any of the primary clauses unsatisfied, then there are at least some null flips available (if not positive flips).

Proof. If a primary clause is unsatisfied, then the literal (positive or negative) associated to the primary variable of the cluster has truth value 0. When we flip the primary variable, and make this unsatisfied primary clause satisfied, the other primary clause cannot become unsatisfied as a result of this flip. Only the secondary clause in this cluster could become unsatisfied as a result of this flip (but not necessarily). As a consequence, the makebreak value of this flip is greater or equal to zero Δ ≥ 0 .

We have to construct a probability function that will determine the type of flip to be chosen, at each step. Let's assume that at a given moment, we have available N 1 negative flips, N 2 null flips, and N 3 positive flips (where N 1 + N 2 + N 3 represents the number of variables that have unsatisfied clusters). We want to assign a higher probability to the positive and null flips, and a lower probability to the negative flips. We choose a small positive number α. If we assign the probability , to choose a particular negative flip, then the probability to choose any negative flip is α. We also assign the probability . If there are no positive flips available, N 3 = 0 , then we simply take the probability to choose any null flip 1 -α (distributed equally among the null flips available) . If there are no null flips available, N 2 = 0 , then we simply take the probability to choose any

.

  If the current truth valuation of the variable is 0, then with probability 1 increase its truth valuation with 1 𝑀 . If the current truth valuation of the variable is 1, then with probability 1 decrease its truth valuation with

M.

  that the current truth valuation of the corresponding variable is i The probability transition matrix A for each secondary random walk is defined by the transition probabilities: │i -j│ > 1 , for any values of i, j ϵ {0, 1, 2, 3, … … . . , M} .

Theorem 1 .

 1 (convergence theorem for periodic chains). Suppose the Markov chain M is irreducible, has a stationary distribution π , and all states have period d. Let x ∊ S , and let S 0 , S 1 , … … … . , S d-1 be a cyclic decomposition of the state space with x ∊ S 0 . If y ∊ S r , then lim m →∞ p md+r (x, y) = d • π(y) .

..

  The stable distribution of this chain is π(0The chain is periodic with period d = 2. The cyclic decomposition of the state space is S 0 = {0, 1}, S 1 . If we start in state 0, an example of a path taken by this … … … … We see that at any odd time, the chain is in state 1 2 , and at every even time the chain is in state 0 or 1 with equal probability. If we choose a state at random from a given path, we recover the stationary distribution π(0) = π(1M = 4 is considered in [A3].Proposition 5. In the general case, the period is d = 2. If M is an even number, then the cyclic decomposition of the state space is S an odd number, then the cyclic decomposition of the state space is

A

  It can be easily proved that we have the following relations, for 𝑘 ≥ 1.

We note that if the 3SAT expression E has n variables and c clauses, then the clustered expression E* will contain 3c variables, and 4c clauses, out of which c will be three variable clauses and 3c will be two variable clauses.

A cluster associated to a variable x, can be of two types. Type 1 cluster: (x ˅ y ˅ z)˄(x ˅ ˥u)˄(˥x ˅ w)

Here y and z are two literals (they can be positive or negative), and we write ˥𝑥 for the negative literal that represents the negation of x.

Type 2 cluster:

In the clusters above, we will call x the primary variable associated to the cluster, and the other variables are called secondary (but they are primary variables as seen in their own clusters). In a cluster, the three variable clause, and the two variable clause where the primary variable is under the same literal (both positive or bot negative) are called primary clauses. The two variable clause in the cluster in which the primary variable is under an opposite literal (compared to the three variable clause), is called the secondary clause. So a cluster has two primary clauses and a secondary clause.

The most general form of a cluster can be written in the form:

In this case, b, and c can be positive or negative literals, and a is a disjunction of literals, 𝑎 = y ˅ z , b = ˥u , c = w , and x can be a positive or negative literal We construct the truth table of the cluster.

positive flip 1 -α (distributed equally among the positive flips available).

If there are no negative flips available , N 1 = 0 , then we choose a null or positive flip with equal probability 1 2 (distributed equally among the flips available). It is, in principle, possible that at a given moment we only have flips of a certain type available. In that case, the algorithm will choose that type of flip with probability 1. So let's see what is happening. At each step, the algorithm will choose null or positive flips, with high probability (we assume α close to 0), so the number of satisfied clauses can only increase, with high probability (and any negative flips that may occur will be reversed later with high probability). We have to prove that the positive flips occur sufficiently often, so the algorithm is polynomial. This point will be discussed in a future paper.

The clustered Sparrow algorithm

We start with a 3SAT expression E. We construct the clustered expression E*, where each variable appears in at most 3 clauses, as described above.

Repeat 2𝑚 2 times (m is the number of clauses of E*)

If the current truth assignment is a solution, return the solution and stop Choose at random a negative, null or positive flip, according to the probability function described above.

Perform the flip, and update.

Return no solution was found.

So at every step, the algorithm looks only at all the variables that have unsatisfied clusters, and chooses a negative, null or positive flip, according to the probability function described above.

The makebreak idea is discussed in [START_REF] Schöning | [END_REF]. The idea to work with clustered expressions E*, as well as using a probability function that takes into account all the variables at every step (not just those involved in an unsatisfied clause) is original. This algorithm is the result of my collaboration with Dr. Anastasia-Maria Leventi-Peetz (BSI, Germany), but implementation and testing have not been performed yet.