Idea About Why USTCON Is SL-complete
The most important Complete Problem is the USTCON, Lewis and Papadimitriou by their definition showed that USTCON is complete for SL class. They constructed a nondeterministic machine for USTCON, and they made a lemma for converting this machine into Symmetric Turing Machine. Then the theorem follows as any language can be accepted using a symmetric Turing machine is logspace reducible to USTCON as from the properties of the symmetric computation we can view the special configuration as the undirected edges of the graph.
Read more about this topic: Symmetric Turing Machine
Famous quotes containing the word idea:
“I have often inquired of myself, what great principle or idea it was that kept this Confederacy so long together. It was not the mere matter of the separation of the colonies from the mother land; but something in that Declaration giving liberty, not alone to the people of this country, but hope to the world for all future time. It was that which gave promise that in due time the weights should be lifted from the shoulders of all men, and that all should have an equal chance.”
—Abraham Lincoln (1809–1865)