Difference between revisions 1003509 and 1188375 on enwiki

'''James Alden''' (March 31, 1810 - February 6, 1877) was as a U.S. naval officer who served from the late 1820s until after the Civil War.

A native of [[Portland, Maine]], he joined the Navy as a [[midshipman]] in 1828.  As with many naval officers in the pre-Civil War era, promotion came slowly but steadily.  He was promoted to lieutenant in 1841 and commander in 1855.

From 1838-1842, Alden was a participant in the South Sea Exploring Expedition (the "Wilkes Expedition") under Lieutenant [[Charles Wilkes]].  During the [[Mexican-American War]] of 1846-1848 served under Commodore Conner on the Gulf coast of Mexico. 

During the Civil War he was active in the reinforcement of [[Fort Pickens]]; in the expedition against [[Galveston]]; as commander of the ''Richmond'' in the passage of [[Fort Jackson|Forts Jackson]] and [[Fort St Philip|St. Philip]]; in the capture of [[New Orleans]]; and at [[Battle of Vicksburg|Vicksburg]], [[Siege of Port Hudson|Port Hudson]], [[Battle of Mobile Bay|Mobile Bay]], and [[Fort Fisher]]. During the war, he was promoted to the rank of captain, January 2, 1863.  

Alden was promoted to commodore on July 25, 1866, and in 1869 was appointed chief of the [[Bureau of Navigation and Detail]].  Two years later, after his promotion to rear-admiral (June 19, 1871), he became commander of the European squadron. 

Rear Admiral Alden died in [[San Francisco, California]], [[February 6]], [[1877]].

{{bio-stub}}

[[Category:1810 births|Alden, James]]
[[Category:1877 deaths|Alden, James]]
[[Category:U.S. Navy admirals|Alden, James]]
[[Category:Mexican-American War people|Alden, James]]
[[Category:American Civil War people|Alden, JamesIn [[computational complexity theory]], a '''Turing reduction''' from a problem A to a problem B is, intuitively, a [[reduction (complexity)|reduction]] which easily solves B, assuming A is easy to solve. More formally, a Turing reduction is a function computable by an [[oracle machine]] with an oracle for A.

If such a reduction exists, then every [[algorithm]] for ''M'' immediately yields an algorithm for ''L'', formed by inserting a "call" to that algorithm at each place where the oracle machine uses it. However, because the oracle machine may invoke the algorithm a large number of times, the resulting algorithm may require more time asymptotically than either ''M'' or the oracle machine, and require as much space as both together. Turing reductions can be applied to both [[decision problem]]s and [[function problem]]s. 

If C<sup>C</sup> = C for some class of problems C, we say that C is ''closed under Turing reductions''. Demonstrating a Turing reduction from a problem A to a problem in such a class C shows that A &isin; C. Many important [[complexity class]]es such as [[NP (complexity)|NP]] are not closed under Turing reductions. In particular, any decision problem can be Turing-reduced to its complement, by simply solving the original problem and inverting the answer, showing that any class not closed under complement is also not closed under Turing reductions. However, a number of classes within [[P (complexity)|P]], such as [[L (complexity)|L]], [[NL (complexity)|NL]], [[SL (complexity)|SL]], and [[P (complexity)|P]] itself, are closed under Turing reductions.

Where Turing reductions are too powerful, a special case called [[many-one reduction]]s are usually used instead; most natural complexity classes are closed under these. These can be seen as Turing reductions where the oracle can only be invoked one time at the end of the oracle machine's processing.

Turing reductions are often subjected to additional resource restrictions, for example that the oracle machine runs in polynomial time or logarithmic space; see [[polynomial-time reduction]] and [[log-space reduction]] for details.

== References ==
* [http://www.nist.gov/dads/HTML/turingredctn.html NIST Dictionary of Algorithms and Data Structures: Turing reduction]

[[Category:Computational complexity theory]]