edin1’s blog

Computational complexity is the study of what resources, such as time and memory, are needed to carry out given computational tasks, with a particular focus on lower bounds for the amount needed of these resources. Proving any result of this kind is notoriously difficult, and includes the famous problem of whether P = N P . This course will be focused on two major results in the area. The first is a lower bound, due to Razborov, for the number of steps needed to determine whether a graph contains a large clique, if only “monotone” computations are allowed. This is perhaps the strongest result in the direction of showing that P and N P are distinct (though there is unfortunately a very precise sense in which the proof cannot be developed to a proof of the whole conjecture). The second is Peter Shor’s remarkable result that a quantum computer can factorize large integers in

polynomial time. In order to present these two results, it will be necessary to spend some time discussing some of the basic concepts of computational complexity, such as the relationship between Turing machines and the more obviously mathematical notion of circuit complexity, and an introduction to what a quantum computation actually is. For the latter, no knowledge of quantum mechanics will be expected, and scarcely any will be imparted during the course: it is possible to understand quantum computation in a very “pure mathematics” way. The reason this is a graduate course rather than a Part III course is that I intend to give several lectures in an informal style that would be hard to examine. It is not because the material will be more advanced: indeed, my aim will be to make allowances for the fact that people will not be working on it with an exam in mind, and to make the course as easy to follow as I can. Having said that, the main results will be proved in full: the informal discussion will be with a view to making these proofs more comprehensible.

The collection will have 12 graduate level lectures which are currently being given during the Easter term 2009. Many thanks to Adrian Callum-Hinshaw for his help with these video lectures.

via SMS: “Tim Gowers – Computational Complexity and Quantum Compuation”.

via:
http://www.marifah.net/forums/index.php?showtopic=2265&pid=9488&mode=threaded&show=&st=&

The Reality of Truthfulness (Sidq)

As for truthfulness (sidq), Allah says:

“O you who believe! Have fear of Allah (taqwa) and be with the truthful.” (9:120)

“Be among the truthful” because the one who sits with someone is influenced for good and evil. Nature is a thief. A man copies the one he mixes with a lot, even if he is not aware of it. Tarafa said,

Do not ask about a man. Ask about his close companions.
Every man imitates his close companions.

This is the best path to travel for someone who wants to discipline himself. It is to mix with the perfect man so that his nature and good habits flow to him. The influence of actions is absolutely stronger than the influence of words.

Al-Qushayri noted, “Truthfulness is the basis of the matter and it is made perfect by it, and it is commanded.” He said, “The least truthfulness is when what is secret and what is public are the same.”

Sahl said, “The scent of truthfulness has not been smelt by any person who flatters wither himself or another person.”

“Truthfulness is the sword of Allah,” said Dhu’n-Nun al-Misri. “It is not applied to anything but that it cuts right through it.”

Al-Harith al-Muhasibi said, “The truthful man is the one who does not care if his entire worth in the hearts of men should vanish away if it is for the sake of putting his heart in harmony. He does not like people to know about his least good actions, and he does not dislike people being aware of his bad actions. If he dislike that, it is proof that he desires to be greater in their eyes. This is not sincerity of the truthful ones.”

It is said that if you seek truthfulness from Allah, He will give you a mirror in which you can see the baseless falsehood of this world and the Next.

The master, Abu’l-Qasim al-Junayd, said, “The truthful man is turned about forty times a day, while the show-off is fixed in the same state for forty years.”

By this, he means that the truthful man changes direction with the truth, no matter what it is. When sees something in the Shari’a which is considered to be excellent, he promptly does it, even if it is at variance with his customary habit. If something arises in the Shari’a which is more important, but he cannot combine the two things, then he moves to the better one. He continues to behave like that. In a single day, he may have a hundred different states, or a thousand or even more, according to his mastery of gnosis, and the manifestation to him of fine points and subtleties.

The show-off, on the other hand, clings to one state alone, and if something arises which the Shari’a considers more important in some states, then he will still not do that important thing. He will hold fast to his state, because he is showing off his worship and his state to creation. He fears that people will stop loving him if he changes. He is very careful to ensure that their love continues. But the truthful one desires only the Face of Allah by his worship. Whenever the Shari’a gives greater weight to a certain state, he goes to that state, and does not turn to creation.

-Imam Abu Zakariyya Muhyi’d-din ibn Sharaf an-Nawawi, The Garden of the Gnostics (Bustan-ul-Arifeen)

The Shadhili Tariqa is built on the foundations of Shukr and Mahabba, gratitude to Allah, and love for him. Moulay Abd as-Salam ibn Mashish summed up the way of the Tariqa that his greatest student was to found in his famous advice to the brethren:

“Seek four things after four things:

Love for Allah,

Satisfaction with the Decree of Allah,

Indifference of the heart towards worldly things, and

Reliance on Allah.

Attain these four, after these four:

Performing Allah’s commands,

Avoiding Allah’s prohibitions,

Patience and fortitude from everything that does not concern one, and

Abandoning everything that distracts and diverts one.”

Were this admonition the only piece of knowledge we had of the Sheikh, it would be enough to prove the truth of his immense understanding, and his lofty status before Allah.

via Murid’s Log: Moulay Abd as-Salam ibn Mashish.