formulasearchengine - User contributions [en]

Flow coefficient

2013-12-23T10:44:27Z

5.57.6.15: /* References */

In [[mathematics]], the '''rank''' of a [[differentiable map]] ''f'' : ''M'' → ''N'' between [[differentiable manifold]]s at a point ''p'' ∈ ''M'' is the [[rank (linear algebra)|rank]] of the [[pushforward (differential)|derivative]] of ''f'' at ''p''. Recall that the derivative of ''f'' at ''p'' is a [[linear map]]
:<math>d_p f : T_p M \to T_{f(p)}N\,</math>
from the [[tangent space]] at ''p'' to the tangent space at ''f''(''p''). As a linear map between [[vector space]]s it has a well-defined rank, which is just the [[dimension]] of the [[image (mathematics)|image]] in ''T''''f''(''p'')''N'':
:<math>\operatorname{rank}(f)_p = \dim(\operatorname{im}(T_p f)).</math>

==Constant rank maps==

A differentiable map ''f'' : ''M'' → ''N'' is said to have '''constant rank''' if the rank of ''f'' is the same for all ''p'' in ''M''. Constant rank maps have a number of nice properties and are an important concept in [[differential topology]].

Three special cases of constant rank maps occur. A constant rank map ''f'' : ''M'' → ''N'' is
*an [[immersion (mathematics)|immersion]] if rank ''f'' = dim ''M'' (i.e. the derivative is everywhere [[injective]]),
*a [[submersion (mathematics)|submersion]] if rank ''f'' = dim ''N'' (i.e. the derivative is everywhere [[surjective]]),
*a [[local diffeomorphism]] if rank ''f'' = dim ''M'' = dim ''N'' (i.e. the derivative is everywhere [[bijective]]).

The map ''f'' itself need not be injective, surjective, or bijective for these conditions to hold, only the behavior of the derivative is important. For example, there are injective maps which are not immersions and immersions which are not injections. However, if ''f'' : ''M'' → ''N'' is a smooth map of constant rank then
* if ''f'' is injective it is an immersion,
* if ''f'' is surjective it is a submersion,
* if ''f'' is bijective it is a [[diffeomorphism]].

Constant rank maps have a nice description in terms of [[local coordinates]]. Suppose ''M'' and ''N'' are smooth manifolds of dimensions ''m'' and ''n'' respectively, and ''f'' : ''M'' → ''N'' is a smooth map with constant rank ''k''. Then for all ''p'' in ''M'' there exist coordinates (''x''1, ..., ''x''''m'') centered at ''p'' and coordinates (''y''1, ..., ''y''''n'') centered at ''f''(''p'') such that ''f'' is given by
:<math>f(x^1,\ldots,x^m) = (x^1,\ldots, x^k,0,\ldots,0)\,</math>
in these coordinates.

==Examples==
[[Image:Rotating gimbal-xyz.gif|thumb|300px|[[Gimbal lock]] occurs because the map ''T''3 → '''RP'''3 does not have rank 3 at all points. This animation shows a set of three gimbals mounted together to allow ''three'' degrees of freedom generically (rank 3 at regular points). When all three gimbals are lined up (in the same plane), the system can only move in two dimensions from this configuration, not three – it has rank 2 at such a singular point – and is in ''gimbal lock''. In this case it can pitch or yaw, but not roll (rotate in the plane that the axes all lie in).]]
Maps whose rank is generically maximal, but drops at certain singular points, occur frequently in [[coordinate system]]s. For example, in [[spherical coordinates]], the rank of the map from the two angles to a point on the sphere (formally, a map ''T''2 → ''S''2 from the [[torus]] to the sphere) is 2 at regular points, but is only 1 at the north and south poles ([[zenith]] and [[nadir]]).

A subtler example occurs in [[charts on SO(3)]], the [[Rotation group SO(3)|rotation group]]. This group occurs widely in engineering, due to 3-dimensional rotations being heavily used in [[navigation]], [[nautical engineering]], and [[aerospace engineering]], among many other uses. Topologically, SO(3) is the [[real projective space]] '''RP'''3, and it is often desirable to represent rotations by a set of three numbers, known as [[Euler angles]] (in numerous variants), both because this is conceptually simple, and because one can build a combination of three [[gimbal]]s to produce rotations in three dimensions. Topologically this corresponds to a map from the 3-torus ''T''3 of three angles to the real projective space '''RP'''3 of rotations, but this map does not have rank 3 at all points (formally because it cannot be a [[covering map]], as the only (non-trivial) covering space is the hypersphere ''S''3), and the phenomenon of the rank dropping to 2 at certain points is referred to in engineering as ''[[gimbal lock]].''

==References==

*{{cite book | first = John | last = Lee | year = 2003 | title = Introduction to Smooth Manifolds | series = Graduate Texts in Mathematics '''218''' | location = New York | publisher = Springer | isbn = 978-0-387-95495-0}}

[[Category:Smooth functions]]

European Union energy label

2013-08-19T09:50:39Z

5.57.6.20: /* Tyres */

In [[computational complexity theory]], '''SL''' ('''Symmetric Logspace''' or '''Sym-L''') is the [[complexity class]] of problems [[log-space reducible]] to '''USTCON''' (''undirected s-t connectivity''), which is the problem of determining whether there exists a path between two vertices in an [[undirected graph]], otherwise described as the problem of determining whether two vertices are in the same [[Connected component (graph theory)|connected component]]. This problem is also called the '''undirected reachability problem'''. It does not matter whether [[many-one reduction|many-one reducibility]] or [[Turing reduction|Turing reducibility]] is used. Although originally described in terms of [[symmetric Turing machine]]s, that equivalent formulation is very complex, and the reducibility definition is what is used in practice.

USTCON is a special case of [[STCON]] (''directed reachability''), the problem of determining whether a directed path between two vertices in a [[directed graph]] exists, which is complete for [[NL (complexity)|NL]]. Because USTCON is '''SL'''-complete, most advances that impact USTCON have also impacted '''SL'''. Thus they are connected, and discussed together.

In October 2004 [[Omer Reingold]] showed that '''SL''' = '''[[L (complexity)|L]]'''.

== Origin ==

SL was first defined in 1982 by Lewis and Papadimitriou,<ref>{{citation
| last1 = Lewis | first1 = Harry R. | author1-link = Harry R. Lewis
| last2 = Papadimitriou | first2 = Christos H. | author2-link = Christos Papadimitriou
| contribution = Symmetric space-bounded computation
| doi = 10.1007/3-540-10003-2_85
| location = Berlin
| mr = 589018
| pages = 374–384
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = Proceedings of the Seventh International Colloquium on Automata, Languages and Programming
| volume = 85
| year = 1980}}.</ref> who were looking for a class in which to place USTCON, which until this time could, at best, be placed only in [[NL (complexity)|NL]], despite seeming not to require nondeterminism. They defined the [[symmetric Turing machine]], used it to define SL, showed that USTCON was complete for SL, and proved that
: <math>\mathrm{L} \subseteq \mathrm{SL} \subseteq \mathrm{NL}</math>
where [[L (complexity)|L]] is the more well-known class of problems solvable by an ordinary [[deterministic Turing machine]] in logarithmic space, and NL is the class of problems solvable by [[nondeterministic Turing machines]] in logarithmic space. The result of Reingold, discussed later, shows that in fact, when limited to log space, the symmetric Turing machine is equivalent in power to the deterministic Turing machine.

== Complete problems ==

By definition, USTCON is complete for SL (all problems in SL reduce to it, including itself). Many more interesting complete problems were found, most by reducing directly or indirectly from USTCON, and a compendium of them was made by Àlvarez and Greenlaw.<ref>{{citation
| last1 = Àlvarez | first1 = Carme
| last2 = Greenlaw | first2 = Raymond
| doi = 10.1007/PL00001603
| issue = 2
| journal = Computational Complexity
| mr = 1809688
| pages = 123–145
| title = A compendium of problems complete for symmetric logarithmic space
| volume = 9
| year = 2000}}.</ref> Many of the problems are [[graph theory]] problems. Some of the simplest and most important SL-complete problems they describe include:
* USTCON
* Simulation of symmetric Turing machines: does an STM accept a given input in a certain space, given in unary?
* Vertex-disjoint paths: are there ''k'' paths between two vertices, sharing vertices only at the endpoints? (a generalization of USTCON, equivalent to asking whether a graph is ''k''-edge-connected)
* Is a given graph a [[bipartite graph]], or equivalently, does it have a [[graph coloring]] using 2 colors?
* Do two undirected graphs have the same number of [[Connected component (graph theory)|connected components]]?
* Does a graph have an even number of connected components?
* Given a graph, is there a cycle containing a given edge?
* Do the [[spanning forest]]s of two graphs have the same number of edges?
* Given a graph where all its edges have distinct weights, is a given edge in the [[minimum weight spanning forest]]?
* [[Exclusive or]] 2-[[Boolean satisfiability problem|satisfiability]]: given a formula requiring that ''x''''i'' xor ''x''''j'' hold for a number of pairs of variables (''x''''i'',''x''''j''), is there an assignment to the variables that makes it true?

The [[complement (complexity)|complement]]s of all these problems are in SL as well, since, as we will see, SL is closed under complement.

From the fact that '''L''' = '''SL''', it follows that many more problems are SL-complete with respect to log-space reductions: every problem in '''L''' or in '''SL''' is '''SL'''-complete; moreover, even if the reductions are in some smaller class than '''L''', '''L'''-completeness is equivalent to '''SL'''-completeness. In this sense this class has become somewhat trivial.

== Important results ==
There are well-known classical algorithms such as [[depth-first search]] and [[breadth-first search]] which solve USTCON in linear time and space. Their existence, shown long before '''SL''' was defined, proves that '''SL''' is contained in '''P'''. It's also not difficult to show that USTCON, and so '''SL''', is in '''NL''', since we can just nondeterministically guess at each vertex which vertex to visit next in order to discover a path if one exists.

The first nontrivial result for '''SL''', however, was [[Savitch's theorem]], proved in 1970, which provided an algorithm that solves USTCON in log2 ''n'' space. Unlike depth-first search, however, this algorithm is impractical for most applications because of its potentially superpolynomial running time. One consequence of this is that USTCON, and so '''SL''', is in DSPACE(log2''n'').<ref>{{citation
| last = Savitch | first = Walter J. | author-link = Walter Savitch
| journal = Journal of Computer and System Sciences
| mr = 0266702
| pages = 177–192
| title = Relationships between nondeterministic and deterministic tape complexities
| volume = 4
| year = 1970
| doi=10.1016/S0022-0000(70)80006-X}}.</ref> (Actually, Savitch's theorem gives the stronger result that '''NL''' is in DSPACE(log2''n'').)

Although there were no (uniform) ''deterministic'' space improvements on Savitch's algorithm for 22 years, a highly practical probabilistic log-space algorithm was found in 1979 by Aleliunas et al.: simply start at one vertex and perform a random walk until you find the other one (then accept) or until ''|V|''3 time has passed (then reject).<ref>{{citation
| last1 = Aleliunas | first1 = Romas
| last2 = Karp | first2 = Richard M. | author2-link = Richard M. Karp
| last3 = Lipton | first3 = Richard J. | author3-link = Richard J. Lipton
| last4 = Lovász | first4 = László | author4-link = László Lovász
| last5 = Rackoff | first5 = Charles | author5-link = Charles Rackoff
| contribution = Random walks, universal traversal sequences, and the complexity of maze problems
| doi = 10.1109/SFCS.1979.34
| location = New York
| mr = 598110
| pages = 218–223
| publisher = IEEE
| title = [[Symposium on Foundations of Computer Science|Proceedings of 20th Annual Symposium on Foundations of Computer Science]]
| year = 1979}}.</ref> False rejections are made with a small bounded probability that shrinks exponentially the longer the random walk is continued. This showed that '''SL''' is contained in [[RL (complexity)|RLP]], the class of problems solvable in polynomial time and logarithmic space with probabilistic machines that reject incorrectly less than 1/3 of the time. By replacing the random walk by a universal traversal sequence, Aleliunas et al. also showed that '''SL''' is contained in [[L/poly]], a non-uniform complexity class of the problems solvable deterministically in logarithmic space with polynomial [[advice (complexity)|advice]].

In 1989, Borodin et al. strengthened this result by showing that the [[complement (complexity)|complement]] of USTCON, determining whether two vertices are in different connected components, is also in '''RLP'''.<ref>{{citation
| last1 = Borodin | first1 = Allan | author1-link = Allan Borodin
| last2 = Cook | first2 = Stephen A. | author2-link = Stephen Cook
| last3 = Dymond | first3 = Patrick W.
| last4 = Ruzzo | first4 = Walter L.
| last5 = Tompa | first5 = Martin
| doi = 10.1137/0218038
| issue = 3
| journal = SIAM Journal on Computing
| mr = 996836
| pages = 559–578
| title = Two applications of inductive counting for complementation problems
| volume = 18
| year = 1989}}.</ref> This placed USTCON, and '''SL''', in co-'''RLP''' and in the intersection of '''RLP''' and co-'''RLP''', which is [[ZPLP]], the class of problems which have log-space, expected polynomial-time, no-error randomized algorithms.

In 1992, [[Noam Nisan|Nisan]], [[Endre Szemerédi|Szemerédi]], and [[Avi Wigderson|Wigderson]] finally found a new deterministic algorithm to solve USTCON using only log1.5 ''n'' space.<ref>{{citation
| last1 = Nisan | first1 = Noam | author1-link = Noam Nisan
| last2 = Szemerédi | first2 = Endre | author2-link = Endre Szemerédi
| last3 = Wigderson | first3 = Avi | author3-link = Avi Wigderson
| contribution = Undirected connectivity in O(log1.5n) space
| doi = 10.1109/SFCS.1992.267822
| pages = 24–29
| title = Proceedings of 33rd Annual Symposium on Foundations of Computer Science
| year = 1992}}.</ref> This was improved slightly, but there would be no more significant gains until Reingold.

In 1995, Nisan and Ta-Shma showed the surprising result that '''SL''' is closed under complement, which at the time was believed by many to be false; that is, '''SL''' = co-'''SL'''.<ref>{{citation
| last1 = Nisan | first1 = Noam | author1-link = Noam Nisan
| last2 = Ta-Shma | first2 = Amnon
| id = {{ECCC|1994|94|003}}
| journal = Chicago Journal of Theoretical Computer Science
| mr = 1345937
| at = Article 1
| title = Symmetric logspace is closed under complement
| year = 1995}}.</ref> Equivalently, if a problem can be solved by reducing it to a graph and asking if two vertices are in the ''same'' component, it can also be solved by reducing it to another graph and asking if two vertices are in ''different'' components. However, Reingold's paper would later make this result redundant.

One of the most important corollaries of '''SL''' = co-'''SL''' is that '''L''''''SL''' = '''SL'''; that is, a deterministic, log-space machine with an [[oracle machine|oracle]] for '''SL''' can solve problems in '''SL''' (trivially) but cannot solve any other problems. This means it does not matter whether we use Turing reducibility or many-one reducibility to show a problem is in '''SL'''; they are equivalent.

A breakthrough October 2004 paper by [[Omer Reingold]] showed that USTCON is in fact in [[L (complexity)|L]].<ref>{{citation
| last = Reingold | first = Omer | author-link = Omer Reingold
| doi = 10.1145/1391289.1391291
| issue = 4
| journal = [[Journal of the ACM]]
| mr = 2445014
| pages = 1–24
| title = Undirected connectivity in log-space
| volume = 55
| year = 2008}}.</ref> Since USTCON is '''SL'''-complete, this implies that '''SL''' = '''L''', essentially eliminating the usefulness of consideration of '''SL''' as a separate class. A few weeks later, graduate student Vladimir Trifonov showed that USTCON could be solved deterministically using O(log ''n'' log log ''n'') space—a weaker result—using different techniques.<ref>{{citation
| last = Trifonov | first = Vladimir
| doi = 10.1137/050642381
| issue = 2
| journal = [[SIAM Journal on Computing]]
| mr = 2411031
| pages = 449–483
| title = An ''O''(log ''n'' log log ''n'') space algorithm for undirected ''st''-connectivity
| volume = 38
| year = 2008}}.</ref>

==Consequences of L = SL ==

The collapse of '''L''' and '''SL''' has a number of significant consequences. Most obviously, all '''SL'''-complete problems are now in '''L''', and can be gainfully employed in the design of deterministic log-space and polylogarithmic-space algorithms. In particular, we have a new set of tools to use in [[log-space reduction]]s. It is also now known that a problem is in '''L''' if and only if it is log-space reducible to USTCON.

==Footnotes==
<references/>

==References==
*<div id="Papadimitriou">[[Christos H. Papadimitriou|C. Papadimitriou]]. ''Computational Complexity''. Addison-Wesley, 1994. ISBN 0-201-53082-1.</div>
*<div id="Sipser">[[Michael Sipser]]. ''Introduction to the Theory of Computation''. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X.</div>

{{ComplexityClasses}}

{{DEFAULTSORT:Sl (Complexity)}}
[[Category:Complexity classes]]